# Why does $2^{O(\log n)} = n^{O(1)}$ hold?

I was recently looking at the article on the P complexity class on Wikipedia. In the section on relationships to other classes, it mentions that P is known to be at least as large as L, giving this explanation:

A decider using $O(\log n)$ space cannot use more than $2^{O(\log n)} = n^{O(1)}$ time.

The article sadly fails to explain how that last equality holds. How exactly does one go about showing that $2^{O(\log n)} = n^{O(1)}$?

## 2 Answers

This is simple math. An expression of the type $O(\log n)$ is at most $C\log n$ for some $C > 0$ and large enough $n$. So for large enough $n$, the entire expression $2^{O(\log n)}$ is at most $$2^{C\log n} = n^C = n^{O(1)}.$$ The first equation follows from the definition of the logarithm $2^{\log n} = n$, which in this case I conveniently assumed is taken to the base 2 (though it makes no difference in this case – can you see why?).

This follows from a little bit of algebraic manipulation of these expressions:

$$2^{c \log n} = (2^{\log n})^c = n^c = n^{O(1)}.$$

Alternatively, if you prefer:

$$2^{c \log n} = 2^{\log(n^c)} = n^c = n^{O(1)}.$$