5.2.1 Tight bounds: the \Theta notation

The definitions for big-O and \Omega give us ways to describe the upper and lower bounds for an algorithm. 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 in \Theta(h) if it is both in O(h) and in \Omega(h).

Almost all algorithms we will discuss in this book have the same tight bound as their upper bound, for example, binary search is in \Theta(\log(n)), sequential search is in \Theta(n), and the sorting algorithms in Chapter 2 are all in \Theta(n\log(n)).

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.

5.2.2 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) if and only if f\in O(g) and f\not\in\Omega(g)

Strict lower bound (\omega)

f\in\omega(g) if and only if f\in\Omega(g) and f\not\in O(g)

5.2.3 Summary of asymptotic notations

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. For example, O(f)\in O(g) means the same thing as f\in O(g), O(f) = O(g) means the same as f\in\Theta(g), O(f) > O(g) means the same as f\in\omega(g), and so on.

5.2.4 Asymptotic equivalence

Asymptotic equivalence is an even stricter notion than the tight bound, meaning that if two functions f and g are asymptotically equivalent, then f\in\Theta(g).

Asymptotic equivalence

f \sim g if and only if f(n)/g(n) \rightarrow 1 (when n \rightarrow \infty)

This notion does not disregard all constants – the multiplicative constants of the fastest-growing term will be kept. For example, the following function:

f(n) = 5 n^2 - 7 n + 100 \log_2(n) + 10^9

is asymptotically equal to 5n^2 when n \rightarrow \infty, or in other words, f(n) \sim 5n^2. This notion can be used to compare different algorithms within the same complexity class, but it is even more difficult to reason about than the tight bound.

Interestingly, asymptotic equivalence has an alternative definition in terms of the strict lower bound: f \sim g if and only if (f-g) \in o(g). It is nice mathematical exercise to show that this is true, from the definitions above.

5.2.5 Classifying functions using limits

We defined asymptotic equivalence using limits, and this is also possible for 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 f/g as n grows towards infinity: k = \lim_{n \rightarrow \infty} f(n)/g(n). The following table summarises the possibilities for k: