0
$\begingroup$

I know that this question is asked a lot of time but I don't understand or I think, I got lost when I was reading Introduction to algorithms

They said, "It is not contradictory, however, to say that the worst-case running time of insertion sort is Omega(n^2), since there exists an input that causes the algorithm to take Omega(n^2) time.".

I read many articles that Omega is the best-case. As I understand correct me if I'm wrong, that the best-case is Omega notation and why they said, "since there exists an input that causes the algorithm to take Omega(n^2) time.", I don't understand why they called it worst-case and why I can call it Omega(n^2), isn't Big O for worst-case.

Also I don't understand they said, "Theta is notation is a stronger notion than Big O". Why is that? and When should I call an algorithm that it's Big O of whatever, Theta or Omega?

Because I'm confused and I don't know which one is for or how to use them.

$\endgroup$
2
  • $\begingroup$ $\Omega$ expresses a lower bound on a function. In that paragraph the function is $n\mapsto$ the running time of the input of size $n$ that makes the algorithm do the largest number of comparisons. $\Omega$ is not about algorithms, or instances of the problems that they solve. Likewise $O$ expresses an upper bound for a function, not running time of any algorithm. $\endgroup$ – plop Aug 26 '20 at 13:52
  • $\begingroup$ When you hear someone saying "This algorithm runs in $O(n)$ operations", it is loose language that omits what is the function that is being talked about. This is OK under the assumption that the reader can infer that they mean the function in the comment above. Those notations, however can be used for other functions, like $n\mapsto$ the running time for an input of size $n$ that takes the least amount of comparisons. One just need to say which function is being talked about. $\endgroup$ – plop Aug 26 '20 at 14:07
1
$\begingroup$

Check the definitions, e.g. in Hildebrand's Introduction to asymptotics. In a nutshell, for the usual computer science use for running times (all relevant functions positive), it is said that:

  • $f(n) = O(g(n))$ if there are $n_0$ and $c > 0$ so that for all $n \ge n_0$ it is $f(n) \le c g(n)$
  • $f(n) = \Omega(g(n))$ if there are $n_0$ and $c > 0$ so that for all $n \ge n_0$ it is $f(n) \ge c g(n)$
  • $f(n) = \Theta(g(n))$ if both $f(n) = O(g(n))$ and $f(n) = \Theta(g(n))$.

Note that the last implies two possibly different $n_0$ values, and different values for $c$ (one each for $O$ and $\Omega$).

Informally, $O(\cdot)$ gives an upper bound, $\Omega(\cdot)$ gives a lower bound, while $\Theta(\cdot)$ gives a sharp bound.

Some examples:

$\begin{align*} n &= O(2^n) \\ (3/2)^n &= \Omega(n^3) \\ n^2 (\sin n + \cos n) &= \Theta(n^2) \end{align*}$}

There are functions that don't have a simple expression, like:

$\begin{align*} f(n) &= \begin{cases} n^2 & n \text{ odd} \\ n^5 & n \text{ even} \end{cases} \end{align*}$

Here clearly $f(n) = \Omega(n^2)$ and $f(n) = O(n^5)$, both best possible among functions $n^\alpha$; there is no simple $g$ so that $f(n) = \Theta(g(n))$.

Lower and upper bounds don't need to be "best possible" in any sense. Often people take great care to get best bounds, but they aren't implied in the notation at all.

To use $\Omega$ to mean best case and $O$ for worst case is misleading at best. For example, the best case for bubblesort on an array of $n$ elements is $\Theta(n)$ (bounded below and above by a linear function in the number of elements; when sorting an already sorted array it does one pass over the data), it's worst case is $\Theta(n^2)$ (if the data are in reverse order). We could say it is $\Omega(n^{1/2})$ and $O(n^3)$ as well, both valid for best and worst cases.

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