# How to prove that $2^{n+3} = O(2^n)$?

I am a little confused on how to prove/disprove Big O.

For the problem, $2^{n+3}= O(2^n)$, I did the following:

$$2^{n+3} \leq K \times 2^n$$

Set $K = 1$

$$2^{n+3} \leq 2^n$$

Test for large values of n (so I plugged in n = 100)

$2^{103} \leq 2^{100}$ --- which is false therefore Big O is disproven

Is this process correct?

• No, it's not correct. $2^{n+3}$ is $O(2^n)$ if there exists a constant $c$ such that $2^{n+3}\le c2^n$ for all large enough $n$. All you have shown is that $c\neq 1$; you need $c=8$. – David Richerby Feb 3 '14 at 23:28
• Thanks. That makes sense. Is there a method to prove them without picking values for 'c' and 'n' or is that the only way? – user13371 Feb 3 '14 at 23:33
• "which is false therefore Big O is disproven" -- wrong. Wrong! Landau notation says something about behaviour in the limit; you can not disprove such a relation with a finite sample! – Raphael Feb 4 '14 at 9:52
• @Raphael, the "it fails for this single case, therefore it is false" is sadly widespread. Here it even adds a parameter $K$, arbitrarily set to 1... – vonbrand Feb 4 '14 at 16:23
• @vonbrand Sad, but probably won't change as long as we keep telling people to just plot it without warning. – Raphael Feb 4 '14 at 17:21

Just, replace the constant $K = 2^3$, and you have to use this constant for your proof.
$$2^{n+3} = K\times 2^n$$
So, $O(2^{n+3}) = O(2^n)$.