Section 7.1 The growth of sequences
Perhaps you have heard the word asymptote before. A horizontal asymptote, if it exists, says that a function “levels out” as its input grows larger and larger. In that same way, asymptotics refers to the behavior of sequences as the index grows without bound.
To get an idea of the problem asymptotics is meant to solve, consider the following example.
Example 7.1.1.
Consider the following example of two programs, \(A\) and \(B\text{,}\) that process some data. The following table provides the number of computations taken by each program to process \(n\) data points.
\(n\) | Program \(A\) | Program \(B\) |
\(1\) | \(1\) | \(58\) |
\(10\) | \(100\) | \(508\) |
\(20\) | \(400\) | \(1,008\) |
\(50\) | \(2,500\) | \(2,508\) |
\(60\) | \(3,600\) | \(3,008\) |
\(100\) | \(10,000\) | \(5,008\) |
\(1000\) | \(1,000,000\) | \(50,008\) |
At first, Program \(A\) looks much better than Program \(B\text{.}\) However, as \(n\) increases, it becomes clear that \(A\) is worse at handling large quantities of data than \(B\text{.}\) If \((A_n)\) and \((B_n)\) represent sequences of the numbers of steps taken by each program, then \(A_n=n^2\) and \(B_n = 50n+8\text{.}\) The way we quantify the relationship between the two sequences is by saying \(A_n\) is "big-O" of \(B_n\text{.}\)
Definition 7.1.2.
Let \(a_n\) and \(b_n\) be terms of sequences. We say \(a_n\) is big-O of \(b_n\) if there exist a real number \(C\) and an integer \(k\) such that for all \(n \ge k\text{,}\)
We write \(a_n = O(b_n)\text{,}\) even if the equals sign is technically incorrect.
This is another technical definition that can be hard to parse, but the idea is that eventually (after the \(k\)-th term of the sequence) \(a_n\) does not grow faster than \(b_n\text{.}\) In this way, \(b_n\) serves as an upper bound on the growth of \(a_n\text{.}\)
Two sequences are depicted as continuous functions. For a while, the red function is below the big function, but then starts to grow much more quickly and continues to grow faster than the blue function. Therefore, the blue function is big-O of the red one.
As we will see again when we discuss partial orders in Part IV, there may be many upper bounds. For example in a classroom of twenty-nine students one may say “Here are fewer than thirty students” or “Here are fewer than a million students.” The first statement is obviously more informative. So often you will be asked to find the least upper bound on the growth of \(a_n\text{;}\) this is usually a \(b_n\) that is the simplest and is itself big-O of all the other options.
Theorem 7.1.4.
Any non-negative sequence is big-O of itself.
Proof.
Let \((a_n)\) be a non-negative sequence; that is, \(a_n \ge 0\) for all \(a_n\text{.}\) Then the statement
is satisfied by equality since \(|a_n| = a_n\text{.}\) If we put \(C=k=1\text{,}\) then this statement implies that \(a_n = O(a_n)\text{.}\)
We can form a basic hierarchy of sequences and their big-O relationships. Memorizing this basic hierarchy will be key to understanding more complicated big-O relationships. In the below table, a sequence \(a_n\) appearing to the left of a sequence \(b_n\) means that \(a_n=O(b_n)\text{.}\)
Slowest | Fastest | |||||||
\(1\) | \(\log n\) | \(n\) | \(n \log n\) | \(n^2\) | Other polynomials | \(2^n\) | Other exponentials | \(n!\) |
At the left-most end of the chart, the slowest-growing sequence is \((a_n) = (1, 1, 1, \ldots)\text{.}\) It is slowest-growing because it does not grow at all! In fact, because the big-O definition allows us to “fudge” the multiplicative constant \(C\text{,}\) any constant sequence is big-O of any other sequence.
The next slowest sequence is the base-\(2\) logarithm.
Definition 7.1.5.
The base-\(2\) logarithm of \(n\) is the number \(\log n\) such that
if and only if
A fun interpretation of \(\log n\) given our recent discussions is that \(\log n\) is roughly the number of digits in the binary expansion of \(n\text{.}\) (Likewise, the familiar \(\log_{10}n\) is roughly the number of digits in the base-\(10\) expansion of \(n\text{.}\))
The rest of the functions in the list should be familiar. Notice that all polynomial functions of higher degrees like \(n^3\) appear between \(n^2\) and \(2^n\text{,}\) and higher-order exponential functions like \(e^n\) occur between \(2^n\) and \(n!\text{.}\)
Now we know where basic functions fit into the big-O hierarchy, but what about more complicated expressions like \(50n+8\text{?}\) The following theorem will help.
Theorem 7.1.6.
Let \((a_n)\) and \((b_n)\) be sequences.
If \(c\) is a nonzero constant, then \(ca_n = O(a_n)\text{.}\)
Suppose there exists a sequence \(c_n\) such that \(a_n = O(c_n)\) and \(b_n=O(c_n)\text{.}\) Then, \(a_n+b_n\) is big-O of \(c_n\) as well.
Suppose there exist sequences \(A_n\) and \(B_n\) such that \(a_n=O(A_n)\) and \(b_n=O(B_n)\text{.}\) Then, \(a_nb_n = O(A_nB_n)\text{.}\)
In plain English, this theorem says:
Constant multiples do not affect growth rate. (Remember, the big-O definition allows us to freely manipulate the constant multiple.)
When adding two sequences, the larger absorbs the smaller. In other words, one must only look at the highest-order term of a sum.
Growth rates are multiplicative. To put it very informally, “big-O of the product is the product of the big-O's.”
It is worthwhile to read the below proof of the theorem, but do not worry if you don't understand it. Read it once, then maybe come back again after you have had more practice with inequalities in the next chapter. You can work the problems at the end of the chapter even if you don't totally understand the following proof.
Proof.
To prove the addition rule (second bullet point), suppose \(a_n = O(c_n)\) and \(b_n = O(c_n)\text{.}\) That means there exist witnesses \(k_1, k_2, C_1,\) and \(C_2\) where \(|a_n| \le C_1c_n\) for all \(n \ge k_1\) and \(|b_n| \le C_2c_n\) for all \(n \ge k_2\text{.}\) Then,
for all \(n \ge \text{max}\{k_1,k_2\}\text{.}\) In other words, this inequality holds for all \(n\) far enough along that both the big-O relationships hold. By definition, this means \(a_n + b_n\) is big-O of \(c_n\text{.}\)
To prove the multiplication rule (third bullet point), suppose there exist sequences \(A_n\) and \(B_n\) such that \(a_n=O(A_n)\) and \(b_n=O(B_n)\text{.}\) Therefore there exist witnesses \(k_1, k_2, C_1,\) and \(C_2\) where \(|a_n| \le C_1A_n\) for all \(n \ge k_1\) and \(|b_n| \le C_2B_n\) for all \(n \ge k_2\text{,}\) so that for all \(n > \text{max}\{k_1, k_2\}\text{,}\)
To prove the theorem about constant multiples (first bullet point), apply the multiplication rule where \((b_n)\) is the constant sequence \((c, c, c, \ldots)\text{.}\) Observe that this sequence is big-O of the sequence \((1)\) by taking \(k=0\) and \(C=1/c\text{.}\) So, since \(a_n = O(a_n)\) and \(c = O(1)\text{,}\) \(ca_n = O(1\times a_n) = O(a_n)\) as claimed.
Finally, we have enough tools to do some examples!
Example 7.1.7.
Consider the sequence whose terms are given by the formula \(a_n = n^2 + 5n + 7\text{.}\) We would like to find the simplest function \(b_n\) of lowest order such that \(a_n=O(b_n)\text{.}\)
Notice that \(a_n\) is a sum of three terms: \(n^2\text{,}\) \(5n\) which is big-O of \(n\text{,}\) and \(7\) which is big-O of \(1\text{.}\) Only the highest-order of these matters; both the constant term and the linear term \(n\) are big-O of \(n^2\text{,}\) but not the other way around. Therefore \(a_n = O(n^2)\text{.}\)
Example 7.1.8.
What is the simplest and lowest-order function \(b_n\) such that \((1 + 5n + 2n^2)(\log n + 3n \log n)\) is big-O of \(b_n\text{?}\)
The addition rule says we only need the highest-order term of each factor, and then the multiplication rule says we must multiply those terms together. The highest-order term of the first factor is big-O of \(n^2\) and the second factor is big-O of \(n \log n\text{;}\) so, the whole sequence is big-O of \(n^3 \log n\text{.}\)
Example 7.1.9.
Order the following functions by growth rate where the slowest-growing function is labeled \(1\text{,}\) the fastest-growing function is awarded the highest number, and if two functions are big-O of one another, they are labeled with the same number. The functions are:
\(15\log n + 3\) | \(n!\) | \(20n^2\) | \(2^n\) | \(n^3\log n\) | \(2022\) | \(n^4\) | \(n!+2^n\) | \(n^2-n+7\) |
These functions may be ordered by combining the basic hierarchy as well as the addition and multiplication rules. Since \(\log n\) grows slower than \(n\text{,}\) the function \(n^3\log n\) grows slower than \(n^3 \cdot n = n^4\text{.}\)
The functions \(n^2-n+7\) and \(20n^2\) are big-O of one another because constant multiples do not affect growth rate. Likewise, since \(n!+2^n = O(n!)\text{,}\) that function and \(n!\) are big-O of one another. The completed table is below.
2 | 7 | 3 | 6 | 4 | 1 | 5 | 7 | 3 |
\(15\log n + 3\) | \(n!\) | \(20n^2\) | \(2^n\) | \(n^3\log n\) | \(2022\) | \(n^4\) | \(n!+2^n\) | \(n^2-n+7\) |
We will end by briefly mentioning two other growth relationships. Recall that to say \(a_n = O(b_n)\) is to say that \(b_n\) is an upper bound on the growth rate of \(a_n\text{.}\) Then saying \(a_n = \Omega(b_n)\) (big-Omega) is to say that \(b_n\) is a lower bound on the growth rate of \(a_n\text{,}\) and \(a_n = \Theta(b_n)\) (big-Theta) is to say that \(a_n\) and \(b_n\) grow in the same way.
Definition 7.1.10.
Let \((a_n)\) and \((b_n)\) be sequences. Then
\(a_n = \Omega(b_n)\) if \(b_n = O(a_n)\) (\(a_n\) is big-Omega of \(b_n\)),
\(a_n = \Theta(b_n)\) if \(a_n = O(b_n)\) and \(b_n = O(a_n)\) (\(a_n\) is big-Theta of \(b_n\))