How to prove that $6n^2 + 20n \notin \Omega{(n^3)}$

1,045

Since the $\Omega$ function refers to asymptotics, the first few cases don't matter.

If $n \ge 10$, then $n^3 > 6n^2 + 20n$. Proof: Since

$$6n + 20 \le 6n + 2n = 8 n < n \cdot n = n^2,$$

multiplying both sides by $n$ gives

$$6n^2 + 20n < n^3.$$

Note: $n \ge 9$ works too, but $n \ge 10$ is just slightly simpler to show.

Share:
1,045
Argus
Author by

Argus

Updated on September 01, 2020

Comments

  • Argus
    Argus about 3 years

    I'm not sure how to go about this, I've tried finding constants and N values to find out, for instance I tried to prove it through contradiction but I must be doing something wrong because I'm getting something that cannot be possible. This is one such example that I tried:

    $N = 1 , c = 1$

    but this is what I get:

    $6(1^2) + 20(1) \geq 0^3 $

    $26 \geq 0$

    which does the opposite. I'm not sure where I'm going wrong with this. Can anyone help me? Thanks in advance.