CODEWITHSUNDEEP
loopsc++11time-complexitybig-ocomplexity-theory
Sayed Alesawy
Sayed Alesawy

Reputation: 445

Algorithm complexity analysis C++

What if i have a loop like this 

for( int i=2 ; i<n ; i=i*i ){ 
    .
    .
}

what the complexity of such a loop would be ?

Upvotes: 1

Views: 152

Answers (4)

wrwrwr
wrwrwr

Reputation: 1066

The loop will execute as long as:

22iteration - 1 < n

or:

iteration < log2(log2(n)) + 1

thus the will be exactly: 

ceil(log2(log2(n)))
iterations. (Assuming n > sqrt(2) and counting iterations from 1.)

Upvotes: 0

Saurav Sahu
Saurav Sahu

Reputation: 13924

Ryan has already answered this question. This is just to explain how on the jth iteration, i is 22j

2         = 2^1 //iteration 0
2 * 2     = 2^2 //iteration 1
2^2 * 2^2 = 2^4 //iteration 2
2^4 * 2^4 = 2^8 //iteration 3
2^8 * 2^8 = 2^16 //iteration 4

y = 22j

log y = 2j

log (log y) = j

Thus, the total number of iterations is log (log y)

Upvotes: 1

Ry-
Ry-

Reputation: 224867

On the jth iteration, i is 22j, so there are O(log log n) iterations.

Upvotes: 2

Robert Columbia
Robert Columbia

Reputation: 6408

If the loop starts at 0, which was the OP's initial question:

It will be an infinite loop unless n<=0. i starts at 0, and 0*0=0. If n<=0, the loop will not execute because the condition i<n would not be met upon loop entry.

Upvotes: 0

Related Questions