3
$\begingroup$

What is the complexity of the following algorithm in Big O:

for(int i = 2; i < n; i = i^i)
{
    ...do somthing
}

I'm not sure if there is a valid operator to this type of complexity. My initial thought was as follows:

After $k$ iterations we want: (using tetration?)

${^{k}i} = n \implies k=\log\log\log..._k\log{n}\implies\mathcal{O(\log\log\log..._k\log{n})}$ (where we have k times the log function) but i'm not sure if this is evan a valid way of writing this. Anyway, we have a complexity that that includes $k$, which does not seems right to me.

$\endgroup$
4
  • 2
    $\begingroup$ I'm assuming the i^i in the code is supposed to refer to exponentiation, and not bitwise XOR as would be suggested by the C-esque syntax? $\endgroup$ – Aaron Rotenberg Aug 26 '20 at 6:04
  • 1
    $\begingroup$ @AaronRotenberg Yes. i to the power of i, not bitwise XOR. $\endgroup$ – Eminem Aug 26 '20 at 6:05
  • $\begingroup$ Given that the largest i≈n, isn't the answer O(RootOf(x**x==n))? I am not sure if it has a closed-form solution. $\endgroup$ – DYZ Aug 26 '20 at 6:12
  • $\begingroup$ (Inverse Ackermann (degree 4)?) $\endgroup$ – greybeard Aug 27 '20 at 7:31
2
$\begingroup$

This sequence is OEIS A173566. To understand how large it grows:

$a_n = 2^{2^{b_{n-1}}}$

where:

$b_0 = 0$

$b_n = b_{n-1} + 2^{b_{n-1}}$

The sequence $b_i$ grows faster than $2^{\cdotp^{\cdotp^{2^0}}}$, where there are $i$ 2's in the tower.

EXPTIME is $O(2^n)$, 2-EXPTIME is $O(2^{2^n})$, and in general, you can define n-EXPTIME . The sequence $b_i$ is not in n-EXPTIME for any natural n. So it, and therefore $a_i$, is not in the complexity class ELEMENTARY.

The definition above shows that $a_i$ is primitive recursive, which is interesting, because that means it doesn't grow as fast as the Ackermann function.

I think (but don't really have the time to formally prove or disprove right now) that means it's $\mathcal{E}^4$ in the Grzegorczyk hierarchy. Left as an exercise.

$\endgroup$
0
$\begingroup$

There is no closed form. The number of loop iterations is 0 if n <= 2, 1 if n <= 4, 2 if n <= 256, 3 if n <= $2^{264}$, 4 if n is less than some number with more than $2^{264}$ digits, so the universe isn’t large enough to write that number down.

The real problem is not the number of iterations, but how long it takes to calculate the last i, which is obviously larger than $n^n$.

$\endgroup$
4
  • 1
    $\begingroup$ Yes, but n can be as large as we want it to be. I understand that no real algorithm will use this type of complexity, but in theory why cant we have a closed form? $\endgroup$ – Eminem Aug 26 '20 at 18:34
  • $\begingroup$ See the last line: The time it takes to calculate the last i^i will be far larger than the number of iterations. The time complexity is for all the operations, not just the loop iterations. $\endgroup$ – gnasher729 Aug 26 '20 at 20:43
  • $\begingroup$ The time it takes to calculate the last i^i is ~T(n^n)=O(n). Why is it larger than O(n^n)? $\endgroup$ – DYZ Aug 27 '20 at 1:29
  • $\begingroup$ " I understand that no real algorithm will use this type of complexity [...]" Eh, don't be so sure. It depends what you mean by "real". There are algorithms which have been published as existence proofs (i.e. just to prove that a problem has a solution) which are of greater complexity than this. $\endgroup$ – Pseudonym Aug 27 '20 at 6:09
0
$\begingroup$

You can compute the number of rounds by a recursive formula. Find an $i$ such that $i^i = n$. But we know that $i = 2^k$. Hence, we should find a $k$ such that $n =(2^k)^{2^k}$. Hence, $\log{n} = 2^k \log{2^k} = k \times 2^k$. Now, if we suppose $n = 2^m$, $m = k\times 2^k = i \log{i}$ and $n = 2^{i \log{i}}$. Hence, if we suppose $T(n)$ is the complexity of the method, $T(n) \leq T(\log(n)) + 1$, as $\log(n) = i \log{i}$ and it means $i \leq \log{n}$. On the other hand, we know that $\log^*(n) = \log^*(\log n) + 1$. Therefore, we can conclude that $T(n) = O(\log^*n)$.

$\endgroup$
2
  • $\begingroup$ Can you explain again the part with the recursive function? How does T(n)<T(log n) +1? What exactly is T? $\endgroup$ – Eminem Aug 26 '20 at 18:33
  • $\begingroup$ @eminem $T(n)$ is the complexity of the method. Please see the update. $\endgroup$ – OmG Aug 26 '20 at 20:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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