Search code examples
algorithmtime-complexitynested-loops

How do you find the asymptotic time complexity of these loops?

How do you find the asymptotic time complexity of this code?

for i=1 to n do
    j=2
    while j<i do
        j=j*j

In my notes I have the answer O(n*log(logn)) but without an explanation.

Solution

  • The first for loop runs n times. The inner loop iterates in squares and so will take O(loglogn) So, total complexity is O(n*log(logn)).

    To understand why iterating in squares take O(log(logn)) time, see this way :

    Suppose n is as large number as 2^16.

    Initially: j = 2
1st step : j = 2^2
2nd step : j = 2^4
3rd step : j = 2^8
4th step : j = 2^16.

    Hence it takes only 4 steps which is loglog(2^16).

    So now for any n = 2^k, you start with 2 and everytime you are squaring. So , there can be atmost O(logk) squaring you can do to reach k. Since n = 2^k, So, k = log(n) and hence O(logk) is same as O(log(logn)).