1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – David Simmons Jul 24 '15 at 23:38
  • $\begingroup$ 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)$ $\endgroup$ – joe Jul 24 '15 at 23:40
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – joe Jul 25 '15 at 0:12
  • 1
    $\begingroup$ @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. $\endgroup$ – vonbrand Jul 25 '15 at 0:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.