[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.
Tell me more
×
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.
|
|
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 ;-) |
|||||
|
|
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. |
|||
|
|
