-1

What is the complexity of the following loop?

    for(i=1;i<n;i=2^i)
       sum+=i;
gnat
  • 21,442
  • 29
  • 112
  • 288
Anshul Negi
  • 11
  • 1
  • 1
    Possible duplicate of [What is O(...) and how do I calculate it?](http://programmers.stackexchange.com/questions/132331/what-is-o-and-how-do-i-calculate-it) – gnat Sep 05 '16 at 14:16
  • 2
    Isn't `^` the bitwise XOR operator? If it is, then this loop will run forever if `n` is greater than 3. – Tanner Swett Sep 05 '16 at 14:19
  • I assume the OP knows what O(...) is, just doesn't know what it would be in this particular case. @TannerSwett: it's "exponent" in many languages as well. – dagnelies Sep 05 '16 at 14:20
  • 1
    On the 5th iteration of the loop, `i` will 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's `slog`. – Ordous Sep 05 '16 at 14:42
  • @ordous correct,at 5 it will try to calculate 2^(2^16),which result in overflow so for what number of iteration it will run for given 'n' – Anshul Negi Sep 05 '16 at 15:26
  • @AnshulNegi How is that not answered by my previous comment?... – Ordous Sep 05 '16 at 16:04
  • How we can derive it mathematically? – Anshul Negi Sep 05 '16 at 18:18
  • @AnshulNegi Your loop step is pretty much the definition of `tetration`. `slog`is the inverse of tetration. What else do you need? – Ordous Sep 05 '16 at 18:28

3 Answers3

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

Community
  • 1
dagnelies
  • 5,415
  • 3
  • 20
  • 26
-1

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.

gnasher729
  • 42,090
  • 4
  • 59
  • 119
-2

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)

ARIJIT DAS
  • 5
  • 2