Is $O(2^{n/2})$ the same as $O(2^n)$?

Question

Why or why not? It seems like the answer should be no, but on the other hand, it's weird that you'd reach the same value in a constant multiple of n.

One may observe that, as $n \to \infty$, $\displaystyle \frac{2^n}{2^{n/2}} \to \infty.$ — Olivier Oloa, Nov 18 '18 at 00:45
a constant multiple of $n$ has big consequences when $n$ is in the exponent — mathworker21, Nov 18 '18 at 00:48

score 2 · Answer 1 · answered Nov 18 '18 at 00:42

2

$2^{n}$ is $O(2^{n})$ but it is not $O(2^{n/2})$.

answered Nov 18 '18 at 00:42

Kavi Rama Murthy

311,013

score 1 · Answer 2 · answered Nov 18 '18 at 03:00

1

By exponent rules, $O(2^{n/2}) = O((2^{1/2})^n) \approx O(1.414^n)$ which clearly differs from $O(2^n)$ by more than a constant factor (consider the ratio).

answered Nov 18 '18 at 03:00

qwr

10,716

score 0 · Answer 3 · answered Nov 18 '18 at 00:52

0

I made the same mistake once but if you write $x=2^n$, then you would have $O(x) = O(x^2)$ which of course doesn't make sense.

answered Nov 18 '18 at 00:52

Stan Tendijck

2,422

This answer doesn't work in general -- what if $x=2$? Then $O(x) = O(x^2) = O(e^x)$, which makes perfect sense (in this context, abusing notation in the way you do it by not viewing $x$ as a variable). – Carl-Fredrik Nyberg Brodda Oct 04 '22 at 17:47

Is $O(2^{n/2})$ the same as $O(2^n)$?

3 Answers3