# Understanding $O$-notation and the meaning of $\Omega$

I am studying algorithms, and I have problems on the concepts from an exercise. Thank you so much!

Which of the following equations lie in $$O(n)$$, $$\Omega(n)$$, $$\Theta(n)$$ and why.

a. $$3n+2n^2$$

b. $$\log {n}+4n^3+6n$$

c. $$5n+6$$

$$O(n)$$: c only
$$\Omega(n)$$: a only
$$\Theta(n)$$: c only

But the answers are saying:
$$O(n)$$: c only
$$\Omega(n)$$: a, b, c
$$\Theta(n)$$: c only

I am confused. Doesn't $$\Omega$$ mean a lower bound on the equation? Then the $$\Omega$$ of $$a, b, c$$ should be:
a: $$\Omega(n)$$
b: $$\Omega(\log n) \leftarrow \Omega(\log n)$$ should be lower than $$\Omega(n)$$
c: $$\Omega(1) \leftarrow$$ much lower than $$\Omega(n)$$

• Why do you think those are the answers? You'll want to make sure you are giving the right answers for the right reasons, not just by random luck. Feb 22, 2013 at 3:02
• You should always look for the dominating terms for $O$ , $\Theta$ and $\Omega$ .In polynomials, it will have the one with largest degree. Feb 22, 2013 at 3:10

Plot the functions... It will make it a lot clearer. $$\Omega (n)$$ means that the function $$f(n)$$ (for large enough $$n$$) will take on values such that $$f(n) > cn$$, where $$c$$ is some constant.

For plot examples, look here:

Problem A (Obviously here, $$f(n) \gg n$$)

Problem B (Again, for large enough $$n$$, $$f(n) \gg n$$)

Problem C (For all $$n$$, $$f(n) \gt n$$)

EDIT: Note that $$\Omega$$ notation is not specifying the term in $$f(n)$$ that grows the slowest, but rather any function that grows slower than the entirety of $$f(n)$$.

• Thank you a lot! it's much clearer from the graph! Feb 22, 2013 at 3:19

Assuming you know $O$ :

If $f(n)=O(g(n))$ then $g(n)=\Omega(f(n) )$.

And $f(n)=\Theta(g(n))$ $\iff$ $f(n)=O(g(n))$ and $f(n)=\Omega(g(n))$ .

So $\Theta$ gives a tight bound.

$O$ gives an upper bound.

$\Omega$ gives a lower bound.

Keep in mind that the function is $\Theta (g(n))$ iff it is both $O(g(n))$ and $\Omega(g(n))$. Hence the answer to (c).