CODEWITHSUNDEEP
algorithmruntimetime-complexitybig-oasymptotic-complexity
paltimea
paltimea

Reputation: 1

Determining O-runtime of simple loop

I have this simple loop in pseudocode:

i = 2

while i < n do
    i = i * i

How would I determine the Big-O for this algorithm with respect to n?

In this case i would go: 2, 4, 16, 256, 65536, etc, each time i itself is squared. I'm not sure how to come up with an expression to describe this.

Upvotes: 0

Views: 45

Answers (1)

OmG
OmG

Reputation: 18838

In first sight the time complexity is O(log(n)) as n in condition of while is static. However, you can find tight bound if scrutinize more. To do this as you follow the steps they are 2^(2^k). For example for k = 0, 1, 2, ... you can see i is growth 2, 4, 16, 246, .... Hence, The exact complexity is O(log(log(n))).

Upvotes: 3

Related Questions