What is the difference between Big O, Omega, and Theta?

Question

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.

Answer 1

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.