Big-O Nested While Loop

Question

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

My shot at this would be O(log n) for the inner loop. And I'm guessing the outer loop is O(n), for an overall complexity of O(n log n). Confirm?

Solution 1

You may proceed formally, step by step, using Sigma notation to obtain the exact number of iterations - Look at Discrete Loops and Worst Case Performance paper (page 10).

The result has been empirically verified.

Solution 2

Yes you are right, but it is not that simple to figure it out correctly :).

Inner loop is trivial log n, there is no need for further explanation.

However the outer loop is not that simple, because in each cycle it changes how long the inner cycle is executed.

If you think about it, the inner cycle will be run for (as i increases) :

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

Due to the some laws of logharitms, it is same as log (1*2*3*4*....*n) which is same as

log (n!)

There is a law that n! has same complexity (beware, it is complexity, it is not same in algebra) as n^n

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

Now we can just switch back to algebra, because log (n^k) = k*log (n) we get the result

log (n^n) = n log n

Result :

Time complexity is O(n log n)

Comments

[AbcAeffchen]

The law is called Stirling's approximation en.wikipedia.org/wiki/Stirling%27s_approximation