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$

Improve this question
$\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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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