3
$\begingroup$

How can I interpret a time complexity of $2^{O(n)}$? Is it simply equal to $O(2^n)$?

I'm pretty new to this, so would appreciate any kind of help.

$\endgroup$
3
$\begingroup$

$O(2^{O(n)})$ means: It is $O(2^{f(n)})$ for some function f with f(n) ≤ cn for large n.

So this could be $O(2^n)$ if c = 1, or $O(2^{2n})$ = $O(4^{n})$ if c = 2, or $O(2^{100n})$ = $O((2^{100})^{n})$ if c = 100. We don't know. All we know is it grows pretty fast, and we can't simply express it as O(something).

| cite | improve this answer | |
$\endgroup$
3
$\begingroup$

The expression "$2^{O(n)}$" is shorthand for "$2^{f(n)}$ for some function $f(n) = O(n)$". For example, $3^n = 2^{O(n)}$. This example also demonstrates that a function which is $2^{O(n)}$ is not necessarily $O(2^n)$, though the opposite does hold.

| cite | improve this answer | |
$\endgroup$

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