What is the complexity of $i^i$? What is the complexity of the following algorithm in Big O:
for(int i = 2; i &lt; 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.
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.