I was looking at the definition of Big Omega:\begin{align} \Omega(g(n)) &= \{ f(n): \text{ there exist positive constants }c \text{ and }n_0 \\ &\ \ \ \ \ \ \ \ \text{ such that }0 \le cg(n) \le f(n) \text{ for all }n \ge n_0 \} \end{align}
I have a function $\frac{n^2+n}2$ to prove that it belongs to $\Omega(n^3)$.
I started like this
$cn^3 \le \frac{n^2+n}2$ but I am not quite sure how do I get $c$, if I pick $n=1$ I get $c\le 1$ but what is the better way of proving this?
$\endgroup$ 51 Answer
$\begingroup$In order to have $\frac{n^2 +n}{2} \in \Omega(n^3)$, you need a positive constant $c$ s.t. for $n\geq n_0$ you have
$$0<cn^3 \leq \frac{n^2 +n}{2}$$
But
$$\frac{n^2 +n}{2n^3} =\frac 12\left(\frac 1n + \frac 1{n^2}\right)\stackrel{n \to \infty}{\longrightarrow}0$$
So, there is no such $c$. Hence, $\frac{n^2 +n}{2}\not \in \Omega(n^3)$
$\endgroup$ 3
