What is the complexity of the following loop?

  • 1
    Possible duplicate of What is O(...) and how do I calculate it? – gnat Sep 5 '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 5 '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 5 '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 5 '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 5 '16 at 15:26

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:



It would be a big O using following this notation:


| improve this answer | |
  • How does it follow from the Big-O notation that it cannot contain non-elementary functions? – Ordous Sep 5 '16 at 18:27
  • @Ordous ...good point ...I don't even know if there is a mathematical expression for the opposite of a tetration – dagnelies Sep 5 '16 at 18:33
  • @Ordous Edited accordingly. thanks for pointing it out. – dagnelies Sep 5 '16 at 18:51
  • Yeah, that's much better :) It does have bounds (obviously!), just nothing that's both precise and easily understandable. – Ordous Sep 5 '16 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.

| improve this answer | |
  • 1
    By ^ the exponent operation is meant of course, not bitwise XOR. – dagnelies Sep 6 '16 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)

| improve this answer | |
  • 2
    Actually, it's 2^1, 2^2, 2^4, 2^16... – Ordous Sep 5 '16 at 20:44

Not the answer you're looking for? Browse other questions tagged or ask your own question.