# 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. – David Simmons Jul 24 '15 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)$ – joe Jul 24 '15 at 23:40

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.
• @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. – vonbrand Jul 25 '15 at 0:35