Time complexity of an algorithm [closed]

Question

Closed. This question needs details or clarity. It is not currently accepting answers.

---

Want to improve this question? Add details and clarify the problem by editing this post.

Closed 4 years ago.

Improve this question

What is the complexity of the following loop?

    for(i=1;i<n;i=2^i)
       sum+=i;

Answer 1

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

Answer 2

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.

Answer 3

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)