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