While loop Time complexity

Question

I have an algorithm exam.. and am a bit not great in the loops time complexity :s I just started to get the basics of it..

I have this while loop

i=2
while (i<n)
{
   i=i*i
   x=x+1
}

I believe that the solution must be like:
(i) will run from 2 to 2^k where k = 2ⁱ
every time it execute the statement 1 time..

so 1+1+1+.. , this means 1*2^k

and from here I can't continue..

the second question guys.. please recommend a site or sth that I can practice some more of these.. searched but didn't find :s

SomeWittyUsername · Accepted Answer · 2013-03-03T12:13:51.907

2

The loop runs as long as the i is less than n. In other words, you need to find k such that 2^{2^k} < n. ==> k = log₂log₂n. So the loop iterates for log₂log₂n times and at each iteration it performs 2 operations (multiplication and addition) - these operations take O(1) time.

==> The time to execute the loop is equal to log₂log₂n * O(1) ==> total complexity is O(loglogn).

edited Mar 03 '13 at 12:13

answered Mar 03 '13 at 11:12

SomeWittyUsername

18,025
3
42
85

Thats What i though.. but wasn't sure about.. Thanks :) – geekybedouin Mar 03 '13 at 11:19
1

If `n=2^64` => `O(lgn) = 64`; however loop executes only 6 times. – जलजनक Mar 03 '13 at 11:37
@icepack so its log^2 or log(logn)?? the second one ryt?? – geekybedouin Mar 03 '13 at 12:49
Yes (it would've been `logn` if power of `i` in each iteration was multiplied by constant) – SomeWittyUsername Mar 03 '13 at 12:53

While loop Time complexity

1 Answers1

Linked