# Understanding big O notation examples

I understand the main idea of big-O-notation, yet I have two questions regarding to the following examples:

Prove/Disprove:
1. $2^{2n+1} = O(2^{2n})$
2. $2^n = O(2^{n\over 2})$

Questions:

1. I looked at the proof showing that the expression equivalent to: $2\cdot 4^n + 3^n = O(4^n)$. Where did the $3^n$ came from?

2. I understood that this statement is false, so lets assume by contradiction it's true that: ${2^n} \le c \cdot {2^{\frac{n}{2}}}$ for all $n\ge n_0$. What should I do next? dividing by ${2^{\frac{n}{2}}}$ brought me an odd result.

Thanks.

-
1. There is no $3^n$, it's definitely a typo. 2. In this "odd result", what happens if you let $n \to \infty$? – Antonio Vargas Mar 9 '14 at 14:32
For 2., you dividing should give you $2^{n/2} \leq c$. Is that what you got? – Darren Naylor Mar 9 '14 at 14:41

1. $2^{2n+1} = 2\cdot 2^{2n}$. Since you always have $f(x) = O\left(f(x)\right)$ and since $f(x) = O\left(g(x)\right)$ implies $c\cdot f(x) = O\left(g(x)\right)$, it follows that $2^{2n+1} = O(2^{2n})$.

2. If $2^n = O\left(2^{\frac{n}{2}}\right)$, then there is a $c$ and an $n_0$ such that for all $n \geq n_0$ you have $2^n \leq c\cdot 2^{\frac{n}{2}}$. (You wrote $n < n_0$, I assume that is a typo). Dividing by $2^{\frac{n}{2}}$ makes this $2^{\frac{n}{2}} \leq c$, and taking the logarithmn plus some rearranging gives $$n \leq 2\log_2 c \text{.}$$ for all $n$ larger than some $n_0$. That can't be true - whatever you pick for $c$, the right side yields some finite value, so there's always an $n$ larger than that value.

-
Great, thank you sir! – AnnieOK Mar 9 '14 at 14:55
@AnnieOK BTW, $f(x) = O\left(g(x)\right)$ can be a bit of a treacherous notation. You won't be able to get around that notation - it's used very wildely - but I suggest that you think of it rather as $f(x) \in O\left(g(x)\right)$. – fgp Mar 9 '14 at 15:02
I see why the last is preferred, thanks for noting this. – AnnieOK Mar 9 '14 at 15:19

Observe that if the limit exists, $$\lim_{n\to\infty}\left|\frac{a_n}{b_n}\right|<\infty\Longleftrightarrow a_n=\mathcal O(b_n)$$

Can you compute $\lim\limits_{n\to\infty}\frac{2^{2n+1}}{2^{2n}}$ and $\lim\limits_{n\to\infty}\frac{2^n}{2^\frac n2}\$?

-