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