0

Let $f(n)=3n^3$ and $g(n) = n^3$ then $f = Ω(g)$ Answer: Let $n_0 = 0$ and $c = 1$

So I know how to find $c$ and $n_0$ for big-oh, like this:

$3n^3 \leq cn^3$ [divide to be left with c]

$= c = 3$ and then $n_0 = 0$

I am not sure how to relate this to finding values for big-omega.

Xoque55
  • 4,384
karambit
  • 171
  • 5
  • 17

1 Answers1

1

f (n) is said to be $ \Omega$(g(n)) if $ \exists$ a positive real constant C and a positive integer $n_0$ such that

f (n) $\displaystyle \geq$ Cg(n) $\displaystyle \forall$ n $\displaystyle \geq$ $n_0$

Big-O gives the uppder bound g(n) for f(n), while Big-omega give the lower bound g(n) for f(n).

runaround
  • 2,210
Win Vineeth
  • 3,504