I need to proove these three sentences:
$g(n) = n + 2n^3-3n^4+4n^5$
- $g(n) = \Omega(n^5) $
- $g(n) \neq \Theta(5n^6)$
- $g(n) = \Omega(nlogn)$
Now, for the Big Omega I have no clue how to do it, for the Big Theta, I am trying to prove by contradiction:
So, I assume that $g(n) = \Omega(5n^6)$ ,it means that $\exists c,n : g(n)\ge c5n^6,\forall n\ge n $. So it means that $n + 2n^3-3n^4+4n^5>= c 5 n^6$ and I was trying something like $ 1/n^4+2/n^2 -3/n+4 \ge c5n $ which is absurd because the first function decreases as n grows and the others grows…But I need it more formal…some help?
For $g(n) = \Omega(n^5) $ I tried this way :
$ n+2n^3-3n^4+4n^5 \ge -3n^4+4n^5 \ge -2n^5+4n^5 \ge n^5, \forall n\ge 0, c=1$
For $g(n) = \Omega(nlogn)$ I tried this way :
$ n+2n^3-3n^4+4n^5 \ge -3n^4+4n^5 \ge -3n^5+4n^5 \ge n^5 \ge n^2 = n*n \ge nlogn, \forall n\ge0, c = 1$
I know it's not very formal but it should be correct, more formal ideas?
Best Answer
1) $g(n) = n+ 2n^3 - 3n^4 + 4n^5$
$\quad\quad\quad \ge (4n-3)n^4$
$\quad\quad\quad \ge n^5$ (for $n > 1$)
$\quad\quad\quad \ge Cn^5$ (for $C=1$ and $n > 1$)
2) $g(n) = n+ 2n^3 - 3n^4 + 4n^5$
$\quad\quad\quad < (n^5)n + n^3(2n^3) + n^2(n^4) + n(n^5)$ $\quad$(for $n > 4$)
$\quad\quad\quad < 5n^6$
$\quad So,$ $g(n) \ne \Omega(5n^6)$
$\quad So,$ $g(n) \ne \Theta(5n^6)$
3) $g(n) = n+ 2n^3 - 3n^4 + 4n^5$
$\quad\quad\quad \ge (4n-3)n^4$
$\quad\quad\quad \ge n(n^4)$ $\quad (for \; n > 1)$
$\quad\quad\quad \ge n^3$
$\quad\quad\quad \ge n(n log(n))$
$\quad\quad\quad \ge C(n log(n)$ $\quad (for \; C = 1$ and $n > 1)$