0
$\begingroup$

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.

$\endgroup$
4
  • 1
    $\begingroup$ 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$) $\endgroup$
    – Steven Stadnicki
    Oct 16, 2017 at 21:00
  • $\begingroup$ Ah, you mean like $n^3 = 2 ^{log_2(n^3)}$ ? But how can we advance from here? $\endgroup$
    – 3nondatur
    Oct 16, 2017 at 21:06
  • $\begingroup$ Rewriting $9^{\log_2n}$ as $n^a$ for some given $a$ might be the most direct approach. Can you do that? $\endgroup$
    – Did
    Oct 16, 2017 at 21:21
  • $\begingroup$ Sorry, I can't find a way to do that. Could you give me a hint ? $\endgroup$
    – 3nondatur
    Oct 16, 2017 at 21:42

1 Answer 1

Reset to default
1
$\begingroup$

$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}} $.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .