Understanding big O notation examples

Question

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.

Answer 1

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}\ $?

Answer 2

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.