6
$\begingroup$

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

$\endgroup$
7
$\begingroup$

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

$\endgroup$
6
$\begingroup$

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)}.$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.