[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
-
3Approximate $\log_2 6$; note $2^3=8$... – 2012-04-14
-
0What do you know about $log_2$ as a function of its argument? – 2012-04-14
-
0@Mark what do you mean by "as a function of its argument"? – 2012-04-14
-
0Well, how would you describe in very general terms how $log_2(x)$ varies with $x$? Like not even going to orders or anything ... – 2012-04-14
-
1$2 < \log_2 6 < 3$ – 2012-04-14
-
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 ;-)
-
0OK so I can go on and say that $2(\log_{2}{6})^n\le2\cdot3^{n}\le{c}\cdot3^{n}$, while $n_{0}=0$ and $c=2$ so it would be true for all $n\ge0$. Is that correct? – 2012-04-15
-
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.