How to prove that $6n^2 + 20n \notin \Omega{(n^3)}$
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.
Argus
Updated on September 01, 2020Comments
-
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.