2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – vonbrand Feb 22 '13 at 3:02
  • $\begingroup$ You should always look for the dominating terms for $O$ , $\Theta$ and $\Omega$ .In polynomials, it will have the one with largest degree. $\endgroup$ – Halil Duru Feb 22 '13 at 3:10
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Thank you a lot! it's much clearer from the graph! $\endgroup$ – Dabinlo Feb 22 '13 at 3:19
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$

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.