Prove or disprove the Big-O of an exponential function

Question

$f(n) = 2^{n+1} = O(2^n)$

Intuitively, I think the statement is false. However, when I go about disproving it, I find that $2^{n+1} = 2^n \cdot 2$, meaning that if there is a constant $C$ larger than $2$, then $|2^{n+1}| \le C|(2^n)|$, thus proving the statement.

Any hints would be greatly appreciated.

You have essentially proved it. You have shown that there is a constant $C$, namely $2$, such that $2^{n+1}\le C\cdot 2^n$. — André Nicolas, May 24 '14 at 04:59
But note that $3^n \not\in O(2^n)$, and $2^{2^{n+1}} \not\in O(2^{2^n})$. — user21820, May 24 '14 at 05:26

score 1 · Answer 1 · answered May 15 '15 at 03:53

1

You have successfully proved that $2^{n+1} \in O(2^n)$ with the implicit constant $2$.

answered May 15 '15 at 03:53

davidlowryduda

91,687

Prove or disprove the Big-O of an exponential function

1 Answers1