# 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$

My answer:
$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. – vonbrand Feb 22 '13 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. – Halil Duru Feb 22 '13 at 3:10

## 3 Answers

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! – Dabinlo Feb 22 '13 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).