How is this example big-omega?

I'm having a bit of difficulty understanding big-omega and big-theta of this particular function which is supposedly Ω(16n + 33)

$5n − 2 = Ω(16n + 33)$

I understand that the there is some constant c that will eventually make the inequality $g(n) >= cf(n)$ true but when I look at the two functions all I see is that $16n +33$ is a much bigger function and I can't see how it could be a lower bound for $5n-2$ where $5n-2$ would eventually be bigger than $16n+33$. It's easy to see that it's $O(16n + 33)$ but I don't understand why it's $Ω(16n + 33)$.

• You are right, $5n-2$ will be smaller than $16n+33$ when $n$ becomes large. But the Landau notation specifies a constant also. You appear to be neglecting this in your attempt to understand. Jul 24, 2015 at 23:38
• So am I supposed to just assume that there exists some constant that will make $Ω(16n+33)$? and then only in obvious cases is it easy to see that there is a difference e.g $5n−2 != Ω(16n^2+33)$ Jul 24, 2015 at 23:40

1 Answer

This means that for some $N_0$ and some $c$ you have that whenever $n \ge N_0$: $$5 n - 2 \ge c (16 n + 32)$$ In this case you can take e.g. $N_0 = 100$, and set up the equation: $$5 N_0 - 2 = c (16 N_0 + 32)$$ which gives $c = 83 / 272$. So if $n \ge 100$:

\begin{align} (5 n - 2) - \frac{83}{272} (16 n + 32) &= \frac{2 n - 200}{17} \\ &\ge 0 \end{align}

which shows that $5 n - 2 = \Omega(16 n + 32)$.

In general, you do something like the above. Pick some convenient $N_0$ value (perhaps "after" your functions start behaving) and try to find a matching $c$ value. Here we could set up and solve an equation, in harder cases you might have to fall back to (crude) estimates, underestimating the left side and overestimating the right hand side.

• Thanks, that makes much more sense. In a situation when I just want to quickly determine whether the function is omega and not calculate the constant c and initial values, is it safe to just look at the largest non-constant terms and make a decision from there and just assume that there exists some constant c that will make the function omega? Jul 25, 2015 at 0:12
• @joe, with a bit of care you can do that. It isn't too hard to prove that a polynomial of degree $k$ is $\Omega(n^k)$, that for $c > 1$ it is $c^n = \Omega(n^r)$ for any $r$, and so on. Check a few such results, they come handy. And if pressed, remembering their proofs will help proving what you are asked. Jul 25, 2015 at 0:35