CODEWITHSUNDEEP
big-ocomplexity-theorytime-complexity
user3818430
user3818430

Reputation: 119

Big-O Nested While Loop

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?

Upvotes: 5

Views: 14659

Answers (2)

Mohamed Ennahdi El Idrissi
Mohamed Ennahdi El Idrissi

Reputation: 2977

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).

enter image description here

The result has been empirically verified.

Upvotes: 8

libik
libik

Reputation: 23029

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)

Upvotes: 1

Related Questions