0

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?

Alfred
  • 103
  • It is not true that $\frac{n^2 +n}{2} \in \Omega(n^3)$. However, $\frac{n^2 +n}{2} \in \mathcal{O}(n^3)$. – Gary Nov 29 '20 at 13:54
  • @Gary why it isn't? for n=1 I get c<= 1 and if I increase n I get c smaller value but greateer than 0 – Alfred Nov 29 '20 at 13:56
  • The $c$ should remain fixed for all sufficiently large values of $n$. Otherwise, the concept would not make much sense. – Gary Nov 29 '20 at 13:57
  • so we have to find a c such as the expression will always be true no matter how much n increases? – Alfred Nov 29 '20 at 13:59
  • Yes, you want a $c$ such that the inequality holds for all $n$ from a certain point (this point is indicated by $n_0$). – Gary Nov 29 '20 at 14:01

1 Answers1

2

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)$

trancelocation
  • 32,243