What is the complexity of the following loop?
for(i=1;i<n;i=2^i)
sum+=i;
8
Despite the apparent simplicity of the question, I think it is quite tricky.
…I’ll go as far as to say it cannot be expressed in “big O” notation …or at least not in the usual sense with logs and exponentials.
Let me explain. In terms of “big O” notation, you should be able to know how many steps are required in terms of n. To do that, you need to know when your i exceed n.
Let me rename it into f for the sake of usual math notation, and j the number of iterations. This boils down to solving the recursive formula:
f(j) = 2^f(j-1)
…which has no solution that can be expressed in terms of “elementary functions” of j (the number of steps) according to:
https://math.stackexchange.com/questions/1741947/closed-form-solution-to-exponential-recursion
EDIT:
It would be a big O using following this notation:
https://en.wikipedia.org/wiki/Super-logarithm
4
Obviously i will cycle between the values 1 and 3 because 2^1 == 3 and 2^3 == 1. The loop will have zero iterations (one test) if n ≤ 1, one iteration (two tests) if n = 2 or n = 3, and it will run forever otherwise.
1
this is an iteration so we have to unfold the loop
say i is taking value 1 to 2^k in the pattern 1,2,4,8,16….2^k
i.e. 2^0,2^1,2^2,2^3 this way
where sum is being executed k times
upto 2^k equals n
2^k=n
k=logn
and
it is O(log n) and also the best worst case is same so the ans will be Theta(logn)
1