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 ?
Add a comment
|
4 Answers
On the jth iteration, i is 22j, so there are O(log log n) iterations.
Comments
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)
Comments
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.
1 Comment
Sayed Alesawy
sorry , i made a mistake , i mean
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.)
