2
$\begingroup$

I'm new to asymptotic notations and right now I'm trying to prove that $n^4 = \mathcal{O}(2^n)$. In my current solution (written below) I used L'Hôpital's rule repeatedly, proving that the limit of $n^4/2^n$ goes to zero. Is this correct? Additionally I'm wondering whehter there is a simpler solution to this problem. I tried induction but didn't get far. If you see an easier solution I would gladly appreciate any hints.

Thanks for any answers.

$ \lim_{n\to\infty} \frac{n^4}{2^n} = \lim_{n\to\infty} \frac{4*n^3}{2^n * ln(2)} = ..... = 0$

$\endgroup$
3
  • $\begingroup$ There is faster solution: $n=2^{\log_2 n}$ $\endgroup$
    – rus9384
    Sep 7, 2017 at 18:29
  • 1
    $\begingroup$ Yes, it is correct. rus9384's suggested solutions is a bit slicker though. $\endgroup$
    – Imago
    Sep 7, 2017 at 18:32
  • $\begingroup$ @Imago, he still would need to prove $1/2^{\lim_{n\to\infty}n-4\log_2 n}\rightarrow 0$. $\endgroup$
    – rus9384
    Sep 8, 2017 at 6:42

1 Answer 1

Reset to default
2
$\begingroup$

You mentioned trying induction, to no avail. However, induction does work. Let's prove by induction that for all $n \geq 6$, $$n^4 \leq \frac{81}{4} 2^n.$$ This is true for $n = 6$ (both sides are equal to 1296). Suppose that it holds for some $n \geq 6$. Then $$ (n+1)^4 = \left(\frac{n+1}{n}\right)^4 n^4 = \left(1 + \frac{1}{n}\right)^4 n^4 \leq \left(1 + \frac{1}{6}\right)^4 n^4. $$ You can calculate that $(7/6)^4 < 2$ (equivalently, $2401 = 7^4 < 2 \cdot 6^4 = 2592$). Therefore, using the induction hypothesis, $$ (n+1)^4 < 2n^4 \leq 2 \frac{81}{4} 2^n = \frac{81}{4} 2^{n+1}. $$ Thus the inequality holds for $n+1$ as well, completing the proof by induction.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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