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