What is the difference between Big O, Omega, and Theta?
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 &gt; 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 &gt; 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
     &amp;= O(2^n) \\
   (3/2)^n
     &amp;= \Omega(n^3) \\
   n^2 (\sin n + \cos n)
     &amp;= \Theta(n^2)
\end{align*}$}
There are functions that don't have a simple expression, like:
$\begin{align*}
   f(n)
     &amp;= \begin{cases}
           n^2 &amp; n \text{ odd} \\
           n^5 &amp; 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 &quot;best possible&quot; 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.