5.2.1 Lower bounds: the $\Omega$ notation

Big-$O$ notation describes an upper bound. In other words, big-$O$ states a claim about the greatest amount of some resource (usually time) that is required by an algorithm for some class of inputs of size $n$.

A similar notation is used to describe the least amount of a resource that an algorithm needs for some class of input. Like big-$O$, this is a measure of the algorithm’s growth rate. And like big-$O$, it works for any resource (usually time), and for some particular class of inputs of size $n$. The lower bound for an algorithm (or a problem, as we will discuss in Section 5.3) is denoted by the symbol $\Omega$, pronounced “big-Omega” or just “Omega”. The following definition for $\Omega$ is symmetric with the definition of big-$O$.

Lower bound

$f\in\Omega(g)$ iff there exist positive numbers $k$ and $n_0$ such that $f(n)\geq k\cdot g(n)$ for all $n>n_0$

It is also true that the equation of the example above is in $\Omega(n)$. However, as with big-$O$ notation, we wish to get the “tightest” (for $\Omega$ notation, the largest) bound possible. Thus, we prefer to say that this running time is in $\Omega(n^2)$.

Recall the sequential search algorithm to find a value within an array of integers. In the worst case this algorithm is in $\Omega(n)$, because in the worst case we must examine at least $n$ values.

5.2.2 Tight bounds: the $\Theta$ notation

The definitions for big-$O$ and $\Omega$ give us ways to describe the upper bound for an algorithm (if we can find an equation for the maximum cost of a particular class of inputs of size $n$) and the lower bound for an algorithm (if we can find an equation for the minimum cost for a particular class of inputs of size $n$). When the upper and lower bounds are the same within a constant factor, we indicate this by using $\Theta$ (big-Theta) notation. An algorithm is said to be $\Theta(h(n))$ if it is in $O(h(n))$ and it is in $\Omega(h(n))$. Note that we drop the word “in” for $\Theta$ notation, because there is a strict equality for two equations with the same $\Theta$. In other words, if $f(n)$ is $\Theta(g(n))$, then $g(n)$ is $\Theta(f(n))$.

Because the sequential search algorithm is both in $O(n)$ and in $\Omega(n)$ in the worst case, we say it is $\Theta(n)$ in the worst case.

Given an algebraic equation describing the time requirement for an algorithm, the upper and lower bounds always meet. That is because in some sense we have a perfect analysis for the algorithm, embodied by the running-time equation. For many algorithms (or their instantiations as programs), it is easy to come up with the equation that defines their runtime behaviour. The analysis for most commonly used algorithms is well understood and we can almost always give a $\Theta$ analysis for them. However, the class of NP-Complete problems all have no definitive $\Theta$ analysis, just some unsatisfying big-$O$ and $\Omega$ analyses. Even some “simple” programs are hard to analyse. Nobody currently knows the true upper or lower bounds for the following code fragment.

while n > 1:
    if n is odd:
        n = 3 * n + 1
    else:
        n = n / 2

But even though $\Theta$ is a more accurate description of the behaviour of an algorithm, we have chosen to almost exclusively use the upper bound big-$O$ notation. The reason for this because it is more difficult to reason about the tight bound than about big-$O$. For example, the simplifying rules for addition and multiplication do not hold for $\Theta$. Another reason is that most other textbooks, research papers, and programmers will usually say that an algorithm is “order of” or “big-$O$” of some cost function, implicitly meaning that this is the tightest possible bound.

5.2.3 Strict bounds

The upper and lower bounds are not strict, meaning that a function is in its own class, $f\in O(f)$ and $f\in\Omega(f)$. We can also define strict versions of upper and lower bounds:

Strict upper bound (little-$o$)

$f\in o(g)$ iff $f\in O(g)$ and $f\not\in\Omega(g)$

Strice lower bound ($\omega$)

$f\in\omega(g)$ iff $f\in\Omega(g)$ and $f\not\in O(g)$

5.2.4 Asymptotic notation and comparing complexity classes

We can summarise the different asymptotic notations ($O$, $o$, $\Omega$, $\omega$, and $\Theta$) in the following table:

All these different bounds correspond to comparison operators between complexity classes:

Using these correspondences and the simplifying rules we can infer the following hierarchy of complexity classes:

$$O(1) < O(\log n) < O(n) < O(n\log n) < O(n^2) < O(n^2\log n) < O(n^3) < \cdots < O(n^k) < O(2^n) < \cdots$$

Zooming in on the very efficient (sub-linear) complexity classes we have:

$$O(1) < O(\log \log n) < O(\log n) = O(\log n^2) = O(\log n^3) < O(\log^2 n) < O(\log^3 n) < O(\sqrt[3]{n}) < O(\sqrt{n}) < O(n)$$

And if we instead look closer on the extreme other end of the scale:

$$\cdots < O(n^1000) < O(1.0001^n) < O(2^n) < O(10^n) < O(1000^n) < O(n!) < O(n^n) < \cdots$$

5.2.5 Classifying functions using limits

There are alternative definitions of the upper, lower and tight bounds. Instead of finding constants $k$ and $n_0$, we can see how the quotient between the two functions behave in the limit.

Given functions $f$ and $g$, we can take the limit of the quotient of the two as $n$ grows towards infinity:

$$\lim_{n \rightarrow \infty} \frac{f(n)}{g(n)}$$

We have the following possibilities: