How to disprove $n^3 = \Omega(9^{\log_2(n)})$

Question

I'm having trouble to disprove the following statement:

$$n^3 = \Omega(9^{\log_2(n)})$$

I'm pretty sure that the claim is false but I'm struggling to falsify it in a formal way. I tried to calculate $$\lim_{n\to\infty} \frac{n^3}{9^{\log_2(n)}}$$

by using L'Hopital's rule in order to apply the limit rule, but this leads to very 'ugly' terms.

Is there a more elegant way to do this?

Thanks in advance for any answers.

Can you figure out how to write $n^3$ in the form $C^{\log_2(n)}$ for some $C$? (Alternately, how to write $9^{\log_2(n)}$ in the form $n^D$ for some $D$) — Steven Stadnicki, Oct 16 '17 at 21:00
Ah, you mean like $n^3 = 2 ^{log_2(n^3)}$ ?
But how can we advance from here? — 3nondatur, Oct 16 '17 at 21:06
Rewriting $9^{\log_2n}$ as $n^a$ for some given $a$ might be the most direct approach. Can you do that? — Did, Oct 16 '17 at 21:21
Sorry, I can't find a way to do that. Could you give me a hint ? — 3nondatur, Oct 16 '17 at 21:42

score 1 · Accepted Answer · answered Oct 16 '17 at 21:51

$n^3 =?\ \Omega(9^{\log_2(n)}) $

$9^{\log_2(n)} =e^{\ln 9\cdot \ln n/\ln 2} =n^{\ln 9/\ln 2} $.

Since $\ln 8/\ln 2 = 3$, $\ln 9/\ln 2 \gt 3$ so $\dfrac{n^3}{9^{\log_2(n)}} =n^{3-\ln 9/\ln 2} \to 0 $ as $n \to \infty$.

Note that $\ln 9/\ln 2 \approx 3.169925$ so that $\dfrac{n^3}{9^{\log_2(n)}} \approx \dfrac1{n^{0.1669925}} $.

How to disprove $n^3 = \Omega(9^{\log_2(n)})$

1 Answers1