Solving recurrence relations, running times, and big-O notation
Last modified: 2026-10-27 13:24:37 (PDT)
Source
The topics of this chapter follow the course calendar and Kameron Decker Harris’s Fall 2026 lecture notes, which name recurrence relations and order of growth as the topics after recursive algorithms. One idea comes from those notes: the running time of a recursive function is the running time of its recursive call plus the work outside it.
Everything else is new: the exercises, the examples, the algorithms pal_loop, table and pairs, the Racket functions, the theorems and their proofs. The algorithms pal and root come from earlier chapters of these notes.
Exercise 1 (Double and add a power of 2) A sequence (Definition: Sequence) starts with \(b_0 = 0\), and for every integer (Definition: Integers) \(n \ge 1\) the term \(b_n\) is twice the term before it, plus \(2^n\). Find \(b_1\), \(b_2\), \(b_3\), \(b_4\) and \(b_5\).
Solution 1. Each term comes from the one before it:
\[ \begin{aligned} b_1 &= 2 \cdot 0 + 2^1 = 2, \\ b_2 &= 2 \cdot 2 + 2^2 = 8, \\ b_3 &= 2 \cdot 8 + 2^3 = 24, \\ b_4 &= 2 \cdot 24 + 2^4 = 64, \\ b_5 &= 2 \cdot 64 + 2^5 = 160. \end{aligned} \]
Definition 1 (Recurrence relation) A recurrence relation (Wikipedia contributors 2026e) is the recurrence of a recursively defined sequence (Definition: Recursively defined sequence), that is, its recursive rule (Definition: Recursive definition) written as an equation, which gives the term \(a_n\) in terms of the \(m\) terms \(a_{n-1}, \ldots, a_{n-m}\) just before it, for every integer \(n \ge n_0 + m\).
Example 1 (The sequence \(b_n\), defined recursively) The sequence of Exercise 1 is recursively defined (Definition: Recursively defined sequence) with \(n_0 = 0\) and \(m = 1\). Its initial term is \(b_0 = 0\), and its recurrence relation (Definition 1) is
\[ b_n = 2 b_{n-1} + 2^n \quad\text{for every integer } n \ge 1. \]
In Racket, where (expt 2 n) is \(2^n\), the recurrence relation becomes a recursive function:
(b 5) leads to calls of (b 4), (b 3), (b 2), (b 1) and (b 0) in turn, and returns 160, as in Solution 1.
Definition 2 (Closed form) A closed form (Wikipedia contributors 2026b) for a sequence \(a_{n_0}, a_{n_0 + 1}, \ldots\) (Definition: Sequence) is a formula for \(a_n\) that uses only \(n\) and fixed numbers, combined by a fixed number of operations such as addition, multiplication, powers and floors (Definition: Floor), and that uses no other term of the sequence.
Example 2 (Closed forms and recurrence relations) The double-minus-one sequence of Example: The double-minus-one sequence, defined recursively has the recurrence relation (Definition 1) \(a_n = 2 a_{n-1} - 1\), which is not a closed form (Definition 2), since it uses the term \(a_{n-1}\). By Theorem: A formula for the double-minus-one sequence, \(a_n = 2^n + 1\) is a closed form for the same sequence: it gives \(a_{50} = 2^{50} + 1\) without finding \(a_1\) through \(a_{49}\) first. Finding a closed form for a sequence from its recurrence relation is called solving the recurrence relation.
Exercise 2 (Using the recurrence relation three times) Let \(b_0, b_1, \ldots\) be the sequence of Example 1, and let \(n \ge 3\). Starting from \(b_n = 2 b_{n-1} + 2^n\), replace \(b_{n-1}\) by \(2 b_{n-2} + 2^{n-1}\), and then replace \(b_{n-2}\) by \(2 b_{n-3} + 2^{n-2}\), to write \(b_n\) in terms of \(b_{n-3}\).
Solution 2. Replacing \(b_{n-1}\) gives \(b_n\) in terms of \(b_{n-2}\):
\[ \begin{aligned} b_n &= 2 \mathopen{}\left(2 b_{n-2} + 2^{n-1}\right)\mathclose{} + 2^n \\&= 4 b_{n-2} + 2^n + 2^n \\&= 4 b_{n-2} + 2 \cdot 2^n. \end{aligned} \]
Replacing \(b_{n-2}\) then gives \(b_n\) in terms of \(b_{n-3}\):
\[ \begin{aligned} b_n &= 4 \mathopen{}\left(2 b_{n-3} + 2^{n-2}\right)\mathclose{} + 2 \cdot 2^n \\&= 8 b_{n-3} + 2^n + 2 \cdot 2^n \\&= 8 b_{n-3} + 3 \cdot 2^n. \end{aligned} \]
Definition 3 (Iteration (unrolling)) Solving a recurrence relation (Definition 1) by iteration, also called unrolling, finds a closed form (Definition 2) for its sequence in three steps:
Example 3 (Unrolling \(b_n = 2 b_{n-1} + 2^n\)) The recurrence relation and Solution 2 give the first steps of iteration (Definition 3) for the sequence of Example 1:
\[ \begin{aligned} b_n &= 2 b_{n-1} + 1 \cdot 2^n, \\ b_n &= 4 b_{n-2} + 2 \cdot 2^n, \\ b_n &= 8 b_{n-3} + 3 \cdot 2^n. \end{aligned} \]
After \(k\) steps the factor in front of \(b_{n-k}\) is \(2^k\), and the multiple of \(2^n\) is \(k\), so the pattern suggests
\[ b_n = 2^k b_{n-k} + k \cdot 2^n \quad\text{for } k = 1, 2, \ldots, n. \]
The initial term is \(b_0\), which is \(b_{n-k}\) when \(k = n\). With \(k = n\) and \(b_0 = 0\),
\[ \begin{aligned} b_n &= 2^n b_0 + n \cdot 2^n \\&= n \cdot 2^n. \end{aligned} \]
This agrees with Solution 1: for example, \(5 \cdot 2^5 = 160 = b_5\).
Remark 1 (Iteration gives a guess). In Example 3, the formula for general \(k\) came from the three cases \(k = 1, 2, 3\). Nothing proved that the pattern continues, so the closed form \(b_n = n \cdot 2^n\) is still a guess. Induction (Definition: Proof by induction) turns such a guess into a theorem, with the recurrence relation in the inductive step.
Exercise 3 (Checking a guess) A sequence starts with \(e_0 = 1\), and has the recurrence relation (Definition 1)
\[ e_n = 3 e_{n-1} + 2^n \quad\text{for every integer } n \ge 1. \]
Someone guesses the closed form (Definition 2) \(e_n = 3^{n+1} - 2^{n+1}\). Find \(e_1\), \(e_2\) and \(e_3\) from the recurrence relation, and check the guess for \(n = 0, 1, 2, 3\).
Solution 3. From the recurrence relation, \(e_1 = 3 \cdot 1 + 2 = 5\), \(e_2 = 3 \cdot 5 + 4 = 19\) and \(e_3 = 3 \cdot 19 + 8 = 65\).
| \(n\) | 0 | 1 | 2 | 3 |
|---|---|---|---|---|
| \(e_n\) | 1 | 5 | 19 | 65 |
| \(3^{n+1}\) | 3 | 9 | 27 | 81 |
| \(2^{n+1}\) | 2 | 4 | 8 | 16 |
| \(3^{n+1} - 2^{n+1}\) | 1 | 5 | 19 | 65 |
The guess is right for \(n = 0, 1, 2, 3\). Four cases do not prove it for every \(n\).
Theorem 1 (A closed form for \(b_n = 2 b_{n-1} + 2^n\)) Let \(b_0, b_1, \ldots\) be the sequence with \(b_0 = 0\) and \(b_n = 2 b_{n-1} + 2^n\) for every integer \(n \ge 1\) (Example 1). Then \(b_n = n \cdot 2^n\) for every non-negative integer (Definition: Non-negative integers) \(n\).
Theorem 2 (A closed form for \(e_n = 3 e_{n-1} + 2^n\)) Let \(e_0, e_1, \ldots\) be the sequence with \(e_0 = 1\) and \(e_n = 3 e_{n-1} + 2^n\) for every integer \(n \ge 1\). Then \(e_n = 3^{n+1} - 2^{n+1}\), as guessed in Exercise 3, for every non-negative integer (Definition: Non-negative integers) \(n\).
Example 4 (A guess that fails) The sequence of Exercise 3 starts \(e_0 = 1\), \(e_1 = 5\), which are \(5^0\) and \(5^1\). So one might guess \(e_n = 5^n\). The guess fails at \(n = 2\), since \(e_2 = 19\) and \(5^2 = 25\).
An attempt to prove the guess by induction (Definition: Proof by induction) shows where it goes wrong. Supposing \(e_k = 5^k\), the recurrence relation gives
\[ \begin{aligned} e_{k + 1} &= 3 e_k + 2^{k + 1} \\&= 3 \cdot 5^k + 2^{k + 1}, \end{aligned} \]
and the inductive step needs this to equal \(5^{k + 1} = 5 \cdot 5^k\), which happens only when \(2^{k + 1} = 2 \cdot 5^k\), that is, only when \(k = 0\).
Remark 2 (Finding a closed form, then proving it). Iteration (Definition 3) and checking small cases, as in Exercise 3, find a closed form (Definition 2) to try. Induction proves it, as in Theorem 1 and Theorem 2, or shows that it is wrong, as in Example 4. A proof by induction needs the closed form before it starts: it can check a formula, but it cannot find one.
Exercise 4 (How many calls does pal make?) Let pal be the algorithm of Exercise: Is it a palindrome?. How many calls of pal, including the first, does pal(abbaabba) make?
Solution 4. pal(abbaabba) calls pal(bbaabb), which calls pal(baab), which calls pal(aa), which calls pal on the empty string, which returns true. That is 5 calls, on strings of 8, 6, 4, 2 and 0 symbols: each call removes the first and last symbols.
Remark 3 (The size of an input and a step). To count the work an algorithm (Definition: Algorithm) does, we first fix two things:
Definition 4 (Running time) Fix, for an algorithm (Definition: Algorithm), the size of an input and what one step is (Remark 3). The running time (Wikipedia contributors 2026f) of the algorithm is the function \(T\) (Definition: Function (map, mapping, transformation)) whose value \(T(n)\) is the largest number of steps that the algorithm takes on any input of size \(n\).
Example 5 (The running time of pal) Take the size (Remark 3) of the input of pal (Exercise: Is it a palindrome?) to be the number \(n\) of symbols in the string, and count each call of pal as one step, since apart from its recursive call each call does at most two comparisons. This assumes that the call on s[2..n-1] passes the shorter string as a pair of positions in s, which takes a fixed number of operations; copying its \(n - 2\) symbols into a new string would add about \(n\) steps to every call. Let \(T(n)\) be the running time (Definition 4). The running time of a call is the running time of its recursive call plus the work outside it.
pal returns without calling itself, so \(T(0) = T(1) = 1\).pal returns at once. It calls pal on a string of \(n - 2\) symbols, which can be any such string, so \(T(n) = T(n - 2) + 1\).Iteration (Definition 3) gives
\[ \begin{aligned} T(n) &= T(n - 2) + 1 \\&= T(n - 4) + 2 \\&= T(n - 6) + 3, \end{aligned} \]
and in general \(T(n) = T(n - 2k) + k\), as long as \(n - 2k \ge 0\). To reach an initial term, take \(k = \mathopen{}\left\lfloor n / 2\right\rfloor\mathclose{}\) (Definition: Floor): then \(n - 2k\) is 0 when \(n\) is even and 1 when \(n\) is odd, and either way \(T(n - 2k) = 1\). So the guess is
\[ T(n) = \mathopen{}\left\lfloor n / 2\right\rfloor\mathclose{} + 1, \]
which gives \(T(8) = 5\), as in Solution 4. Theorem 3 proves it.
Theorem 3 (A closed form for the running time of pal) Let \(T(0) = T(1) = 1\) and \(T(n) = T(n - 2) + 1\) for every integer \(n \ge 2\), as in Example 5. Then \(T(n) = \mathopen{}\left\lfloor n / 2\right\rfloor\mathclose{} + 1\) (Definition: Floor) for every non-negative integer (Definition: Non-negative integers) \(n\).
Exercise 5 (A function that calls itself twice) This Racket function computes the double-minus-one sequence of Example: The double-minus-one sequence, defined recursively, but it finds \(2 a_{n-1}\) as \(a_{n-1} + a_{n-1}\), with two recursive calls:
Write down every call of dm that running (dm 2) involves, counting (dm 2) itself, and the value that each call returns.
Solution 5. (dm 2) calls (dm 1) twice, and each of those calls (dm 0) twice:
That is 7 calls, counting (dm 2) itself, and 4 of them are calls of (dm 0). (dm 2) returns 5, which is \(a_2\). The two calls of (dm 1) do exactly the same work.
Theorem 4 (Two calls of size \(n - 1\) give \(2^n\) base cases) For every non-negative integer (Definition: Non-negative integers) \(n\), the calls that (dm n) of Exercise 5 makes include exactly \(2^n\) calls of (dm 0), counting (dm 0) itself when \(n = 0\). So, counting each call as one step, the running time (Definition 4) of dm satisfies \(T(n) \ge 2^n\).
Remark 4 (One call instead of two). The function dm of Exercise 5 finds the same value \(a_{n-1}\) twice. Writing the recursive rule of Example: The double-minus-one sequence, defined recursively directly, with one recursive call,
returns the same values, but each call of dm1 makes only one recursive call, so its calls form a single chain instead of a tree that doubles at every level. By Theorem 4, (dm 30) makes more than a billion calls, since \(2^{30} = 1073741824\).
Exercise 6 (Which running time is better?) One algorithm takes \(100 n\) steps on an input of size \(n\), and another takes \(n^2\) steps. Compare \(100 n\) with \(n^2\) for \(n = 10, 50, 100, 200, 1000\). Which algorithm takes fewer steps on small inputs, and which on large ones?
Solution 6.
| \(n\) | 10 | 50 | 100 | 200 | 1000 |
|---|---|---|---|---|---|
| \(100 n\) | 1000 | 5000 | 10000 | 20000 | 100000 |
| \(n^2\) | 100 | 2500 | 10000 | 40000 | 1000000 |
The second algorithm takes fewer steps when \(n < 100\), and the two take the same number at \(n = 100\). For every \(n > 100\), \(n^2 = n \cdot n > 100 n\), so the first algorithm takes fewer steps, and the ratio \(n^2 / (100 n) = n / 100\) grows without bound. The factor 100 decides which is better on small inputs; the powers \(n\) and \(n^2\) decide which is better on large ones.
Definition 5 (Big-O) Let \(f\) and \(g\) be functions from the natural numbers to the real numbers. Then \(f(n)\) is big-O of \(g(n)\) (Wikipedia contributors 2026a), written \(f(n) = O(g(n))\), when there exist a real number \(c > 0\) and a natural number \(N\) such that, for every natural number \(n \ge N\), \[ |f(n)| \le c \, |g(n)|. \] In words, from some point \(N\) on, the absolute value of \(f(n)\) is at most a fixed multiple \(c\) of the absolute value of \(g(n)\). The “there exist” is an existential quantifier, and the “for every” is a universal quantifier.
Definition 6 (Witnesses) A real number \(c > 0\) and a natural number \(N\) for which the inequality in Definition 5 holds for every natural number (Definition: Natural numbers (our convention)) \(n \ge N\) are a pair of witnesses for \(f(n) = O(g(n))\). Witnesses for \(f(n) = \Omega(g(n))\) are defined in the same way, from Definition 7. Some books write \(n_0\) for \(N\).
Example 6 (The running time of pal is \(O(n)\)) By Example 5, pal takes \(T(n) = \mathopen{}\left\lfloor n / 2\right\rfloor\mathclose{} + 1\) steps on a string of \(n\) symbols. For every natural number \(n \ge 2\),
\[ \begin{aligned} \mathopen{}\left|T(n)\right|\mathclose{} &= \mathopen{}\left\lfloor n / 2\right\rfloor\mathclose{} + 1 && \text{(} T(n) > 0 \text{)} \\&\le n / 2 + 1 && \text{(definition of the floor)} \\&\le n / 2 + n / 2 && \text{(} 1 \le n / 2 \text{, since } n \ge 2 \text{)} \\&= n, \end{aligned} \]
so \(c = 1\) and \(N = 2\) are witnesses (Definition 6) for \(T(n) = O(n)\) (Definition 5). At \(n = 1\), also \(T(1) = 1 \le 1\), so \(c = 1\) and \(N = 1\) are witnesses too. Witnesses are not unique: any larger \(c\) or \(N\) works as well.
Example 7 (Finding witnesses for \(2 n^3 + 40 = O(n^3)\)) To prove \(2 n^3 + 40 = O(n^3)\) (Definition 5), we look for witnesses (Definition 6) \(c\) and \(N\). Since \(2 n^3 + 40 > 2 n^3\), the term \(2 n^3\) needs \(c > 2\). With \(c = 3\), the inequality \(2 n^3 + 40 \le 3 n^3\) is the same as \(40 \le n^3\), which holds when \(n \ge 4\), since \(4^3 = 64\), but not when \(n = 3\), since \(3^3 = 27\). So for every natural number \(n \ge 4\),
\[ \begin{aligned} \mathopen{}\left|2 n^3 + 40\right|\mathclose{} &= 2 n^3 + 40 && \text{(} 2 n^3 + 40 > 0 \text{)} \\&\le 2 n^3 + n^3 && \text{(} 40 \le 64 \le n^3 \text{, since } n \ge 4 \text{)} \\&= 3 \mathopen{}\left|n^3\right|\mathclose{}, \end{aligned} \]
and \(c = 3\), \(N = 4\) are witnesses. A larger \(c\) allows a smaller \(N\): since \(40 \le 40 n^3\) for every \(n \ge 1\), the pair \(c = 42\), \(N = 1\) also works.
Definition 7 (Big-Omega) Let \(f\) and \(g\) be functions from the natural numbers to the real numbers. Then \(f(n)\) is big-Omega of \(g(n)\) (Wikipedia contributors 2026a), written \(f(n) = \Omega(g(n))\), when there exist a real number \(c > 0\) and a natural number \(N\) such that, for every natural number \(n \ge N\), \[ |f(n)| \ge c \, |g(n)|. \] In words, from some point \(N\) on, the absolute value of \(f(n)\) is at least a fixed positive multiple \(c\) of the absolute value of \(g(n)\). Dividing by \(c\) shows that \(f(n) = \Omega(g(n))\) exactly when \(g(n) = O(f(n))\) in the sense of Definition 5.
Example 8 (\(2 n^3 + 40 = \Omega(n^3)\)) For every natural number \(n \ge 1\),
\[ \begin{aligned} \mathopen{}\left|2 n^3 + 40\right|\mathclose{} &= 2 n^3 + 40 && \text{(} 2 n^3 + 40 > 0 \text{)} \\&\ge 2 n^3 && \text{(} 40 \ge 0 \text{)} \\&= 2 \mathopen{}\left|n^3\right|\mathclose{}, \end{aligned} \]
so \(c = 2\) and \(N = 1\) are witnesses (Definition 6) for \(2 n^3 + 40 = \Omega(n^3)\) (Definition 7).
Definition 8 (Big-Theta) Let \(f\) and \(g\) be functions from the natural numbers to the real numbers. Then \(f(n)\) is big-Theta of \(g(n)\) (Wikipedia contributors 2026a), written \(f(n) = \Theta(g(n))\), when both \(f(n) = O(g(n))\) (big-O) and \(f(n) = \Omega(g(n))\) (big-Omega). In words, \(f(n)\) and \(g(n)\) are within fixed multiples of each other, from some point on.
Example 9 (\(2 n^3 + 40 = \Theta(n^3)\)) By Example 7, \(2 n^3 + 40 = O(n^3)\), and by Example 8, \(2 n^3 + 40 = \Omega(n^3)\). So \(2 n^3 + 40 = \Theta(n^3)\) by Definition 8. The constant 40 and the factor 2 do not change how fast \(2 n^3 + 40\) grows.
Theorem 5 (Sums of big-O functions) Let \(f\), \(g\) and \(h\) be functions (Definition: Function (map, mapping, transformation)) from the natural numbers (Definition: Natural numbers (our convention)) to the real numbers (Definition: Real numbers). If \(f(n) = O(h(n))\) and \(g(n) = O(h(n))\) (Definition 5), then \(f(n) + g(n) = O(h(n))\).
Exercise 7 (Is \(n \cdot 2^n\) big-O of \(2^n\)?) By Theorem 1, the sequence of Example 1 has \(b_n = n \cdot 2^n\). Show that \(n \cdot 2^n = O(2^n)\) (Definition 5) is false.
Solution 7. We use proof by contradiction (Definition: Proof by contradiction). Suppose \(n \cdot 2^n = O(2^n)\), with witnesses (Definition 6) \(c > 0\) and \(N\). Then \(n \cdot 2^n \le c \cdot 2^n\) for every natural number \(n \ge N\), and dividing by \(2^n > 0\) gives \(n \le c\) for every natural number \(n \ge N\).
Let \(n = N + \mathopen{}\left\lfloor c\right\rfloor\mathclose{} + 1\), where \(\mathopen{}\left\lfloor c\right\rfloor\mathclose{}\) is the floor (Definition: Floor) of \(c\). Then \(n\) is a natural number with \(n \ge N\), so \(n \le c\). But \(\mathopen{}\left\lfloor c\right\rfloor\mathclose{} + 1 > c\) by the definition of the floor, and \(N \ge 1\), so \(n > c\). This is a contradiction, so \(n \cdot 2^n = O(2^n)\) is false.
Remark 5 (How to disprove a big-O bound). The statement \(f(n) = O(g(n))\) (Definition 5) says that there exist \(c > 0\) and \(N\) such that every \(n \ge N\) has \(\mathopen{}\left|f(n)\right|\mathclose{} \le c \mathopen{}\left|g(n)\right|\mathclose{}\). Its negation says that for every \(c > 0\) and every \(N\), some natural number \(n \ge N\) has \(\mathopen{}\left|f(n)\right|\mathclose{} > c \mathopen{}\left|g(n)\right|\mathclose{}\), by the rules for negating the existential (Definition: Existential quantifier) and universal (Definition: Universal quantifier) quantifiers. So a disproof cannot pick \(c\) and \(N\): like Solution 7, it takes any \(c\) and \(N\) and finds such an \(n\), which depends on \(c\) and \(N\). Checking that the inequality fails for a few chosen \(c\) and \(N\) is not a disproof.
Exercise 8 (Seven functions at \(n = 16\)) Here \(\log_2 n\) is the power to which 2 must be raised to give \(n\), so \(\log_2 16 = 4\) since \(2^4 = 16\), and \(n!\) is the product \(1 \cdot 2 \cdots n\). Find the values at \(n = 16\) of
and put the values in increasing order.
Solution 8.
| \(1\) | \(\log_2 n\) | \(n\) | \(n \log_2 n\) | \(n^2\) | \(2^n\) | \(n!\) |
|---|---|---|---|---|---|---|
| 1 | 4 | 16 | 64 | 256 | 65536 | 20922789888000 |
The values are already in increasing order. For \(n!\), \(1 \cdot 2 \cdots 16 = 20922789888000\), about \(2 \times 10^{13}\).
Definition 9 (Logarithm) Let \(b > 1\) be a real number (Definition: Real numbers). For every real number \(x > 0\), the logarithm of \(x\) to the base \(b\) (Wikipedia contributors 2026d), written \(\log_b x\), is the real number \(y\) with \(b^y = x\) (Definition: Power with a real exponent).
Example 10 (Some logarithms) By Definition 9,
The logarithm \(\log_2 n\) grows by 1 each time \(n\) doubles: \(\log_2 (2 n) = \log_2 n + 1\), since \(2^{\log_2 n + 1} = 2 \cdot 2^{\log_2 n} = 2 n\).
Remark 6 (The base of a logarithm is a constant factor). For every real number \(x > 0\), let \(y = \log_{10} x\) (Definition 9). Then \(x = 10^y = \mathopen{}\left(2^{\log_2 10}\right)\mathclose{}^y = 2^{y \log_2 10}\), so \(\log_2 x = \log_2 10 \cdot \log_{10} x\). The factor \(\log_2 10\), about 3.32, does not depend on \(x\), so \(\log_2 n = \Theta(\log_{10} n)\) (Definition 8), with \(c = \log_2 10\) and \(N = 1\) as witnesses (Definition 6) for both the big-O and the big-Omega bound. For this reason big-O bounds often write \(\log n\) without a base.
Definition 10 (Factorial) For a natural number (Definition: Natural numbers (our convention)) \(n\), the factorial of \(n\) (Wikipedia contributors 2026c), written \(n!\), is the product \(1 \cdot 2 \cdots n\) of the natural numbers from 1 to \(n\).
Example 11 (Some factorials) By Definition 10, \(1! = 1\), \(3! = 1 \cdot 2 \cdot 3 = 6\) and \(5! = 1 \cdot 2 \cdot 3 \cdot 4 \cdot 5 = 120\). The number of orders in which 5 different books can stand on a shelf is \(5! = 120\): 5 choices for the first, then 4 for the second, and so on.
Theorem 6 (A chain of growth rates) For every natural number (Definition: Natural numbers (our convention)) \(n \ge 4\),
\[ 1 \le \log_2 n < n \le n \log_2 n < n^2 \le 2^n \le n!, \]
where \(\log_2\) is the logarithm to the base 2 (Definition 9) and \(n!\) is the factorial (Definition 10).
Remark 7 (The common growth rates). By Theorem 6, each function in the chain
\[ 1, \quad \log_2 n, \quad n, \quad n \log_2 n, \quad n^2, \quad 2^n, \quad n! \]
is big-O (Definition 5) of the next, with witnesses (Definition 6) \(c = 1\) and \(N = 4\). In the other direction, none is big-O of the one before it. Solution 7 shows how to prove such a statement for \(n \cdot 2^n\) and \(2^n\), and the same argument, dividing by \(n\) instead of \(2^n\), shows that \(n^2 = O(n)\) is false. A running time that is \(\Theta\) (Definition 8) of one of these functions is called, in order,
Other powers of \(n\) fit between \(n\) and \(2^n\). For natural numbers \(a \le b\), \(n^a \le n^b\) for every natural number \(n\), so \(n^a = O(n^b)\). Every power \(n^a\) is also \(O(2^n)\), though the witness \(N\) grows with \(a\): for example, \(n^4 \le 2^n\) holds for every \(n \ge 16\), where \(16^4 = 65536 = 2^{16}\), but not for \(n = 15\), since \(15^4 = 50625 > 32768 = 2^{15}\). We do not prove the general statement here.
Exercise 9 (Printing a multiplication table) The algorithm table, in the pseudocode of Remark: How to read the pseudocode in this chapter, prints a multiplication table:
Here print x writes the value of x as output. How many times does the line print i * j run, as a function of \(n\)?
Solution 9. For each value of \(i\), the inner loop runs print i * j once for each of \(j = 1, 2, \ldots, n\), that is, \(n\) times. The outer loop makes \(n\) passes, one for each of \(i = 1, 2, \ldots, n\), so the line runs \(n + n + \cdots + n = n \cdot n = n^2\) times, once for each entry of an \(n\) by \(n\) table. For example, when \(n = 4\) it runs \(4 \cdot 4 = 16\) times.
Remark 8 (Counting the steps of loops). To find the running time (Definition 4) of an algorithm with loops:
Each test of a loop’s guard (Definition: Guard of a loop) and each line of setup is also a step, but counting them too changes the count by at most a fixed multiple plus a fixed number, which does not change a \(\Theta\) bound (Definition 8) on a count that is at least 1.
Example 12 (A loop, then a nested loop) The algorithm pairs takes an array A[1..n] of numbers, where \(n \ge 1\):
Count each run of an assignment inside a loop as one step. The first loop takes \(n\) steps, and the nested loops take \(n \cdot n = n^2\) steps, as in Solution 9, so the algorithm takes \(f(n) = n + n^2\) steps. Since \(n \le n^2\) and \(n^2 \le n^2\) for every natural number \(n\), both \(n = O(n^2)\) and \(n^2 = O(n^2)\) (Definition 5) with witnesses (Definition 6) \(c = 1\), \(N = 1\), so \(f(n) = O(n^2)\) by Theorem 5. Also \(f(n) \ge n^2\), so \(f(n) = \Omega(n^2)\) (Definition 7) with \(c = 1\), \(N = 1\). So \(f(n) = \Theta(n^2)\) (Definition 8): the nested loops decide the growth, and the first loop does not.
Example 13 (A loop with the same recurrence as pal) The algorithm pal_loop tests whether a string is a palindrome (Definition: Palindrome) with a loop instead of recursion:
The test s[i] = s[j] is made only when i < j is true. Let \(L(n)\) be the largest number of passes through the body on a string of \(n\) symbols. When \(n \le 1\), the guard is false at once, so \(L(0) = L(1) = 0\). When \(n \ge 2\), the most passes come when the first and last symbols match; after the first pass, the loop then runs exactly as it would on the string \(s[2..n-1]\) of \(n - 2\) symbols, with every index one larger. So \(L(n) = L(n - 2) + 1\), the same recurrence relation (Definition 1) as for pal in Example 5, with initial terms one smaller.
So \(L(n) = \mathopen{}\left\lfloor n / 2\right\rfloor\mathclose{}\) (Definition: Floor), by strong induction (Definition: Proof by strong induction) as in the proof of Theorem 3: if \(n \le 1\), then \(L(n) = 0 = \mathopen{}\left\lfloor n / 2\right\rfloor\mathclose{}\), and if \(n \ge 2\) and the formula holds for \(n - 2\), then \(L(n) = \mathopen{}\left\lfloor(n - 2) / 2\right\rfloor\mathclose{} + 1 = \mathopen{}\left\lfloor n / 2\right\rfloor\mathclose{} - 1 + 1 = \mathopen{}\left\lfloor n / 2\right\rfloor\mathclose{}\). The guard is tested once more than the body runs, \(\mathopen{}\left\lfloor n / 2\right\rfloor\mathclose{} + 1\) times, which is the number of calls of pal by Theorem 3, and is \(O(n)\) by Example 6.
Example 14 (root takes \(\Theta(\sqrt{n})\) steps) The algorithm root of Exercise: Tracing a square-root loop returns \(r = \mathopen{}\left\lfloor\sqrt{n}\right\rfloor\mathclose{}\) (Definition: Square root), the largest integer whose square is at most \(n\), and its body adds 1 to r on each pass, starting from 0. So on input \(n\) the body runs exactly \(\mathopen{}\left\lfloor\sqrt{n}\right\rfloor\mathclose{}\) times. Let \(f(n) = \mathopen{}\left\lfloor\sqrt{n}\right\rfloor\mathclose{}\), for natural numbers \(n\).
So \(f(n) = \Theta(\sqrt{n})\) (Definition 8). Since \(\sqrt{n} \le n\) for \(n \ge 1\), the body of root runs no more times than the body of a loop with \(n\) passes: on \(n = 10^6\), its body runs \(1000\) times.