[THIS IS HOMEWORK, Please do not post solutions, just help me understand]
I know this is kind of a CS related question, however I was told this might be the right place to post the question. I'm trying to prove that $2(\log_{2}{6})^{n}=O(3^{n})$ so I started the proof: Following the Big O definition, if $2(\log_{2}{6})^{n}=O(3^{n})$ then there exists $c\ge0$ and $n_{0}\ge0$ such that $2(\log_{2}{6})^{n}\le{c\times3^{n}}$, $\forall{n ≥ n_{0}}$. I tried to rewrite the inequality like $2(\log_{2}{6})^{n}\le{c\times({log_{2}{8}})^{n}}$ then I got stuck. 10x in advance.Big O Notation Proof
-
2Forget about the $2$ in front. It is best not to argue in your *formal* proof that **if** the result you are trying to prove is true, $\dots$. It's OK to think that way while fooling around. Now is there a $c_1$ such that after a while $(\log_2 6)^n \le c_1 3^n$? How big is $\log_2 6$? Now that you have found $c_1$, go back to the original problem. – 2012-04-14
2 Answers
Some hints:
Lemma 1: $c \cdot f(n) = O(f(n))$.
Lemma 2: $c_1 \leq c_2 \Rightarrow c_1^n = O(c_2^n)$.
Example proof technique: To prove that $f(n) = O(g(n))$ you need to show the existence of $c > 0$ and $n_0$ such that $\forall n > n_0.\ f(n) \leq c\cdot g(n)$. The simplest way to do this is to construct such $c$, i.e. give it by formula or just plainly state the evaluated number. To give you an example, I will prove that for non-negative $f$ and $g$ and $k \geq 0$, if $f(n) = O(g(n))$ then $\big(f(n)\big)^k = O\Big(\big(g(n)\big)^k\Big)$.
To show the above, I need to find $c$ and $n_0$ such that $f^k(n) \leq c\cdot g^k(n)$ for all $n > n_0$. But we know that $f(n) = O(g(n))$, that means $\exists d > 0.\ \exists m_0.\ \forall m > m_0.\ f(m) \leq d\cdot g(m). \tag{$*$}$ Let fix $d$ and $m_0$ to be any constants that fulfill $(*)$. Then set $n_0 = m_0$ and $c = d^k$ (this is the point where I construct $c$ and $n_0$, now I only need to show that those values are the constants we are looking for). But $\forall m > m_0.\ f(m) \leq d\cdot g(m)$ so raising both sides to $k$-th power we get $\forall m > m_0.\ f^k(m) \leq d^k\cdot g^k(m)$ but this is literary equivalent to $\forall n > n_0.\ f^k(n) \leq c\cdot g^k(n)$ so our constants do suffice and thus we have (constructively) proved that $\exists c > 0.\ \exists n_0.\ \forall n > n_0.\ f^k(n) = O(g^k(n)).$
Hope that helps ;-)
-
0Exactly. Have fun! :-) – 2012-04-15
Since $3 = log_2 8$ and $log_2 6 \leq log_2 8 = 3$, it holds true for all $ n \geq 1 $ that $({log_2 6})^n \leq 3^n $.
Now what you need to do is to choose the $ c $ and $ n_0 $ constants, so that you can derive the big O inequality from the inequality above.