For a homework problem, we've been asked to prove the following:
$$6n^2+20n \in O(n^3)$$
$$6n^2+20n \not \in \Omega(n^3)$$
Since BigO is defined as $g(n) \leq c \cdot f(n)$ for a function $f(n)$, set of functions $g(n)$, some real constant $c$ and non-negative integer $N$ such that for all $n\geq N$, I worked the first part to
$$6n^2+20n \leq c \cdot n^3$$
$$\frac{6n^2+20n}{n^3} \leq \frac{cn^3}{n^3}$$
$$\frac{6n+20}{n^2} \leq c , n \geq 1$$
Therefore, for $c=26$ and $N=1$, this function satisfies the requirements of Big O.
My issue is that Big $\Omega$ is an identical formula, with the exception of flipped inequality. In order to prove the second part, I need show that no possible $c$ will work.
However, for $n=0, c=0$,
$$\frac{6(0)+20}{0^3} \geq 0 \Rightarrow 0\geq 0$$ which is true.
I also did some more thinking and came up with this series:
$$\frac{6n^2+20n}{c} \geq \frac{c \cdot n^3}{c}$$
$$\frac{6n^2+20n}{c} \geq n^3$$
However, plugging in $n=1$ results in $\frac{26}{c}\geq 1$, meaning this inequality holds true for all $c > 26$
How can I show that no possible $c$ value will work for the second equation?
Best Answer
According to the definition I know, $6n^2+20n\in\Omega(n^3)$ means that there exists a positive number $c$ such that $6n^2+20n\ge c n^3$ for almost all $n$.
Apart from your problematic dividing by $0$, you seem to look for a different $c$ for each $n$. That is not the correct thing to do. Let $c>0$ be given. For which $n$ does $6n^2+20n\ge cn^3$ hold? Divide both sides by $n^2$ to obtain $6+\frac{20}n\ge cn$. Now the left hand side is $\le 26$ for all $n\ge 1$, whereas the right hand side becomes arbitrarily large and thus is $>26$ for almost all $n$ (for which $n$ exactly, depends on $c$, though). Hence for no positive $c$ the required inequality holds for almost all $n$.