# Double exponentials vs single exponentials

Here are four tenets I cannot reconcile:

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.

• I've edited the tags and tile since, really, this question has nothing to do with complexity theory: it's about mathematical notation and the asymptotic behaviour of mathematical functions. Commented Jul 21, 2018 at 15:15

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.

• That convention is the only sensible one. As you described choosing the other way of grouping would be useless since we could already express that value/function using $a^{b\cdot c}$ instead of a fancy "double exponential". Commented Jul 20, 2018 at 21:24
• @Bakuriu Oh, indeed, though it's important to note that it is just a convention. (There could also be the convention to always use parentheses, which is what LaTeX does: it refuses to guess how to group a^b^c, and throws an error instead.) Commented Jul 21, 2018 at 3:04
• All notation is "just a convention". Describing "$a^{b^c}=a^{(b^c)}$" as "just a convention" suggests that there are other plausible alternatives but, really, there aren't. Commented Jul 21, 2018 at 15:14
• @DavidRicherby Certainly, all notation is conventional! But that doesn't mean it's not worth noting. It's a deliberate choice by mathematicians to use that notation: and it's a good choice, because it eliminates ambiguity and is more useful than the alternative. But it's still a choice, and nothing stops you from defining it differently (besides confusing readers for no real gain). Commented Jul 21, 2018 at 16:45
• @Bakuriu I wouldn't go so far as to say it's the only sensible convention, because it seems to me very sensible to assume that all operations are evaluated left-to-right, unless there are parentheses. That's what we do with addition and subtraction and what kids learn in grade school with "PEMDAS". The fact that exponentiation doesn't follow the convention has tripped up me in the past, and just about everyone who first learns about it. Commented Jul 22, 2018 at 5:45

$a^{(b^c)}$ is not the same as $(a^b)^c$. When people write $2^{2^k}$, they usually mean $2^{(2^k)}$, not $(2^2)^k$.