Double exponentials vs single exponentials Here are four tenets I cannot reconcile:


Double exponential time algorithms run in $O(2^{2^{n^k}})$ time with $k \in \mathbb{N}$ constant
Exponential time algorithms run in $O(2^{n^k})$ with $k \in \mathbb{N}$ constant
The former bound grows stricly faster than the latter; i.e., there exist algorithms that run in double exponential time but not in exponential time
Applying $a^{b^c} = a^{bc}$ to the double exponential bound we have $O(2^{2^{n^k}}) = O(2^{2^{nk}}) = O(2^{2nk})$, which falls within the previously stated exponential bound


I feel I am missing some subtlety relating to the definition of an exponential-time algorithm as running in $O(2^{\mathrm{poly}(n)})$ rather than $O(2^{n})$, but I am not sure precisely where the subtlety lies.
The issue comes down to ambiguous terminology.

$(a^b)^c = a^{bc}$, but $a^{(b^c)} \neq a^{bc}$. In other words, exponents aren't associative.

Conventionally, nested exponentials without parentheses are grouped in this second way, because it's more useful. So $2^{2^n} = 2^{(2^n)} \neq 2^{2n}$. If we wanted to talk about $(2^2)^n$, we could just write $2^{2n}$ instead, so we reserve the double exponential notation for the other case.