What is the complexity of the following loop?
for(i=1;i<n;i=2^i)
sum+=i;
3 Answers
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:
-
How does it follow from the Big-O notation that it cannot contain non-elementary functions?Ordous– Ordous2016-09-05 18:27:25 +00:00Commented Sep 5, 2016 at 18:27
-
@Ordous ...good point ...I don't even know if there is a mathematical expression for the opposite of a tetrationdagnelies– dagnelies2016-09-05 18:33:06 +00:00Commented Sep 5, 2016 at 18:33
-
@Ordous Edited accordingly. thanks for pointing it out.dagnelies– dagnelies2016-09-05 18:51:07 +00:00Commented Sep 5, 2016 at 18:51
-
Yeah, that's much better :) It does have bounds (obviously!), just nothing that's both precise and easily understandable.Ordous– Ordous2016-09-05 20:46:03 +00:00Commented Sep 5, 2016 at 20:46
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.
-
1By
^the exponent operation is meant of course, not bitwise XOR.dagnelies– dagnelies2016-09-06 07:39:49 +00:00Commented Sep 6, 2016 at 7:39
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)
-
2Actually, it's 2^1, 2^2, 2^4, 2^16...Ordous– Ordous2016-09-05 20:44:25 +00:00Commented Sep 5, 2016 at 20:44
^the bitwise XOR operator? If it is, then this loop will run forever ifnis greater than 3.iwill have more than 19,000 digits. On the 7th you won't have enough RAM to represent it. For all practical purposes, the loop is O(1). If you want an actual function - it'sslog.