Big-O nested in a loop

Question

i <-- 1
while(i < n)
   j <--1
   while(j < i)
      j <-- j * 2
   i <-- i + 1
done

My shot at this will be O(log n)for the inner loop. And I guess the outer loop is O(n)for the total O(n log n). Confirm?

Answer 1

You can act formally, step by step, using the Sigma notation to get the exact number of iterations. See Binary Loops and Worst Case Studies (page 10).

The result was empirically confirmed.

Answer 2

Yes, you are right, but it’s not so easy to figure it out right :).

The inner loop is trivial log n; no further explanation is needed.

, .

, ( i):

log 1 + log 2 + log 3 + log 4 + log 5 .... + log n

- , log (1*2*3*4*....*n), ,

log (n!)

, n! ​​ (, , ) n^n

log (n!) = O(log (n^n))

, log (n^k) = k*log (n)

log (n^n)= n log n

:

O(n log n)