2.6 Asymptotic analysis

Figure 2.1 gives two views of a graph illustrating the growth rates for six equations. We repeat the graph here, where the right view shows in detail the lower-left portion of the top view. The horizontal axis represents input size, and the vertical axis can represent time, space, or any other measure of cost.

Illustration of the growth rates for six equations

Despite the larger constant for the curve labeled 10n10 n in the figure above, 2n22 n^2 crosses it at the relatively small value of n=5n = 5. What if we double the value of the constant in front of the linear equation? As shown in the graph, 20n20 n is surpassed by 2n22 n^2 once n=10n = 10. The additional factor of two for the linear growth rate does not much matter. It only doubles the xx-coordinate for the intersection point. In general, changes to a constant factor in either equation only shift where the two curves cross, not whether the two curves cross.

When you buy a faster computer or a faster compiler, the new problem size that can be run in a given amount of time for a given growth rate is larger by the same factor, regardless of the constant on the running-time equation. The time curves for two algorithms with different growth rates still cross, regardless of their running-time equation constants. For these reasons, we usually ignore the constants when we want an estimate of the growth rate for the running time or other resource requirements of an algorithm. This simplifies the analysis and keeps us thinking about the most important aspect: the growth rate. This is called asymptotic algorithm analysis. To be precise, asymptotic analysis refers to the study of an algorithm as the input size “gets big” or reaches a limit (in the calculus sense). However, it has proved to be so useful to ignore all constant factors that asymptotic analysis is used for most algorithm comparisons.

In rare situations, it is not reasonable to ignore the constants. When comparing algorithms meant to run on small values of nn, the constant can have a large effect. For example, if the problem requires you to sort many collections of exactly five records, then a sorting algorithm designed for sorting thousands of records is probably not appropriate, even if its asymptotic analysis indicates good performance. There are rare cases where the constants for two algorithms under comparison can differ by a factor of 1000 or more, making the one with lower growth rate impractical for typical problem sizes due to its large constant. Asymptotic analysis is a form of “back of the envelope” estimation for algorithm resource consumption. It provides a simplified model of the running time or other resource needs of an algorithm. This simplification usually helps you understand the behaviour of your algorithms. Just be aware of the limitations to asymptotic analysis in the rare situation where the constant is important.

2.6.1 Orders of growth

To be able to discuss orders of growth for algorithms we need to do some abstractions. The most important abstraction is to describe the runtime of an algorithm as a mathematical function from the input size to a number. We actually don’t care how we encode the input size, as long as it is proportional to the actual size of the input. So we can, e.g., use the number of cells in an array as input, instead of trying to figure out the exact memory usage of the array. And in the same way, we don’t care about the unit of measure for the result – it can be actual runtime, in seconds, minutes or hours, but it’s more common to think about the number of “basic operations”. Already here we have abstracted away lots of things that relate to hardware, which is vital because we want to analyse algorithms, not implementations. So we will say things like “the runtime of algorithm 𝐀\mathbf{A} is f(n)f(n)”.

Now, the easiest way to view order of growth is not as an absolute propery of an algorithm, but instead as a relation between functions. When we say that an algorithm is quadratic, we actually mean that the mathematical function f(n)f(n) that describes the abstract runtime of the algorithm, is related to the quadratic function g(n)=n2g(n) = n^2 in some way.

So, how can we relate functions using orders of growth? We do this by saying that one function is a bound of another function. E.g., when we say that an algorithm 𝐀\mathbf{A} is quadratic, we actually mean that the function n2n^2 is an upper bound of 𝐀\mathbf{A}. The following are informal definitions of upper, lower and tight bounds – we will define them more rigorously in Chapter 5.

Upper bound

ff is an upper bound of gg iff ff grows at least as fast as gg, and we write this f∈O(g)f\in O(g)

Lower bound

ff is a lower bound of gg iff ff grows at most as fast as gg, and we write this f∈Ω(g)f\in\Omega(g)

Tight bound

ff is a tight bound of gg iff both functions grow at the same rate, and we write this f∈Θ(g)f\in\Theta(g)

2.6.2 Should we use OO, Ω\Omega or Θ\Theta?

If an algorithm has a lower bound of Ω(f)\Omega(f), we know that it will never run asymptotically faster than ff. But this is usually not very useful knowledge, because we are more interested in knowing how the algorithm works on on bad inputs. Therefore the upper bound O(f)O(f) is by far the most common complexity measure that people use, and this is what we will be using in this book.

One could argue that Θ(f)\Theta(f) would be an even better measure, because it gives more information about an algorithm. But it is much more difficult to reason about Θ(f)\Theta(f), and therefore we will almost exclusively use the upper bound notation O(f)O(f).

So, is the lower bound useless? – No, definitely not. The main use case for Ω\Omega is when we want to classify problems, not algorithms. One example is when proving that the lower bound for sorting is Ω(nlog⁡n)\Omega(n\log n), which we do in Section 5.3.1. But classifying problems is out of scope for this book, so we will not use Ω\Omega much.