Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
3  
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
1  
$2 < \log_2 6 < 3$ –  Kirthi Raman Apr 14 '12 at 19:54
2  
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
show 1 more comment

2 Answers

up vote 2 down vote accepted

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

share|improve this answer
    
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
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.