f(n) is int result = 0; for (int i = 1; i <= n; i *= 2) for (int j = 0; j <= i; j++) result++; which can be simplified to int result = 0; for (int i = 1; i <= n; i *= 2) result += i+1; which gives sum j=0..⌊log2 n⌋ of 2^j+1 = (sum j=0..⌊log2 n⌋ of 2^j) + ⌊log2 n⌋ + 1 = 2^(⌊log2 n⌋+1) − 1 + ⌊log2 n⌋ + 1 = 2 · 2^⌊log2 n⌋ + ⌊log2 n⌋ n + log2 n − 1 ≤ f(n) ≤ 2n + log2 n so is O(n)