World's most popular travel blog for travel bloggers.

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

, ,
Problem Detail:

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)}\$?

#### Answered By : Yuval Filmus

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