# Big O Notation Proof

[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.

-
Approximate $\log_2 6$; note $2^3=8$... – David Mitra Apr 14 '12 at 19:39
What do you know about $log_2$ as a function of its argument? – Mark Bennet Apr 14 '12 at 19:41
@Mark what do you mean by "as a function of its argument"? – JanosAudron Apr 14 '12 at 19:44
$2 < \log_2 6 < 3$ – Kirthi Raman Apr 14 '12 at 19:54
Forget 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. – André Nicolas Apr 14 '12 at 19:54

## 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 ;-)

-
OK 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? – JanosAudron Apr 15 '12 at 5:26
Exactly. Have fun! :-) – dtldarek Apr 15 '12 at 9:04

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.

-