What is the complexity of $i^i$?

Question

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.

Answer 1

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.

Answer 2

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$.

Answer 3

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)$.