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:
-
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?
-
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.
Best Answer
$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})$.
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.