# Appendix B: Solving Recurrence Equations—With Applications to Analysis of Recursive Algorithms
The analysis of recursive algorithms is not as straight forward as it is for iterative algorithms. Ordinarily, however, it is not difficult to represent the time complexity of a recursive algorithm by a recurrence equation. The recurrence equation must then be solved to determine the time complexity. We discuss techniques for solving such equations and for using the solutions in the analysis of recursive algorithms.
## B.1 Solving Recurrences Using Induction
Mathematical induction is reviewed in [Appendix A](LiB0093.html#1281). Here we show how it can be used to analyze some recursive algorithms. We consider first a recursive algorithm that computes *n*!.
Algorithm B.1: Factorial**![Start example](https://box.kancloud.cn/e95df9d604ab2d89febe370ae4d88fb1_1x1.gif)**Problem: Determine *n*! = *n* (*n* − 1) (*n* − 2) … (3) (2) (1) when *n* ≥ 1.
0! = 1
Inputs: a nonnegative integer *n*.
Outputs: *n*!.
```
int fact (int n)
{
if (n == 0)
return 1;
else
return n * fact (n - 1);
}
```
**![End example](https://box.kancloud.cn/e95df9d604ab2d89febe370ae4d88fb1_1x1.gif)**
To gain insight into the efficiency of this algorithm, let's determine how many times this function does the multiplication instruction for each value of *n*. For a given *n*, the number of multiplications done is the number done when *fact* (*n* − 1) is computed plus the one multiplication done when *n* is multiplied by *fact* (*n* − 1). If we represent the number of multiplications done for a given value of *n* by *tn*, we have established that
![](https://box.kancloud.cn/51ef0b91fbd21d69c696212383d76409_271x64.jpg)
An equation such as this is called a ***recurrence equation*** because the value of the function at *n* is given in terms of the value of the function at a smaller value of *n*. A recurrence by itself does not represent a unique function. We must also have a starting point, which is called an ***initial condition.*** In this algorithm, no multiplications are done when *n* = 0. Therefore, the initial condition is
![](https://box.kancloud.cn/7ecd159f1a7671595e8c6dba5036f971_55x18.jpg)
We can compute *tn* for larger values of *n* as follows:
![](https://box.kancloud.cn/a8e09e9dc7df8f2f035808d7f2e0644f_276x72.jpg)
Continuing in this manner gives us more and more values of *tn*, but it does not enable us to compute *tn*, for an arbitrary *n* without starting at 0. We need an explicit expression for *tn*. Such an expression is called a ***solution*** to the recurrence equation. Recall that it is not possible to find a solution using induction. Induction can only verify that a candidate solution is correct. (Constructive induction, which is discussed in [Section 8.5.4](LiB0072.html#848), can help us discover a solution.) We can obtain a candidate solution to this recurrence by inspecting the first few values. An inspection of the values just computed indicates that
![](https://box.kancloud.cn/798af50762c2e6c61d95d997a0d8d7c3_54x17.jpg)
is the solution. Now that we have a candidate solution, we can use induction to try to prove that it is correct.
Induction base: For *n* = 0,
![](https://box.kancloud.cn/93d867d04e3ab576d77463a2ee1ab062_55x18.jpg)
Induction hypothesis: Assume, for an arbitrary positive integer *n*, that
![](https://box.kancloud.cn/655709f1b9cc412441c5462dce6eb76f_59x18.jpg)
Induction step: We need to show that
![](https://box.kancloud.cn/7046c7b73b86592b7cffe9fe34635273_107x20.jpg)
If we insert *n* + 1 in the recurrence, we get
![](https://box.kancloud.cn/02821c91e91d48a7feab0b3d6032b0e8_300x22.jpg)
This completes the induction proof that our candidate solution *tn* is correct. Notice that we highlight the terms that are equal by the induction hypothesis. We often do this in induction proofs to show where the induction hypothesis is being applied.
There are two steps in the analysis of a recursive algorithm. The first step is determining the recurrence; the second step is solving it. Our purpose here is to show how to solve recurrences. Determining the recurrences for the recursive algorithms in this text is done when we discuss the algorithms. Therefore, in the remainder of this appendix we do not discuss algorithms; rather, we simply take the recurrences as given. We now present more examples of solving recurrences using induction.
Example B.1**![Start example](https://box.kancloud.cn/e95df9d604ab2d89febe370ae4d88fb1_1x1.gif)**Consider the recurrence
![](https://box.kancloud.cn/5f1aea2fb3fbfb7793d99caebc8805f8_358x69.jpg)
The first few values are
![](https://box.kancloud.cn/22072a66f79d0cd0fbbdc410e9c78035_286x104.jpg)
It appears that
![](https://box.kancloud.cn/e9f8dec493829521031a3e99b95709ea_107x19.jpg)
We use induction to prove that this is correct.
Induction base: For *n* = 1,
![](https://box.kancloud.cn/b042241bf5b9eeaa55a05f5f7a26b305_136x20.jpg)
Induction hypothesis: Assume, for an arbitrary *n* > 0 and *n* a power of 2, that
![](https://box.kancloud.cn/baeb776b5b07ea2ebc70340d4beeb4de_107x20.jpg)
Induction step: Because the recurrence is only for power of 2, the next value to consider after *n* is 2*n*. Therefore, we need to show that
![](https://box.kancloud.cn/227fea0ac3d328b8c9b95114620f166c_137x21.jpg)
If we insert 2*n* in the recurrence, we get
![](https://box.kancloud.cn/e3238b304bc32f268b45ff65dc7d8f10_325x74.jpg)
**![End example](https://box.kancloud.cn/e95df9d604ab2d89febe370ae4d88fb1_1x1.gif)**
Example B.2**![Start example](https://box.kancloud.cn/e95df9d604ab2d89febe370ae4d88fb1_1x1.gif)**Consider the recurrence
![](https://box.kancloud.cn/d79557a4bf8f6cfa8392dc0d57d7296d_336x69.jpg)
The first few values are
![](https://box.kancloud.cn/b649d51af449f9d2c068bdd51d5b502d_182x110.jpg)
It appears that
![](https://box.kancloud.cn/9ff013ba57db5b0acf3bca4a1d92d91e_80x23.jpg)
We use induction to prove that this is correct.
Induction base: For *n* = 1,
![](https://box.kancloud.cn/9524460fab7df522dcf6f302c6bee400_151x21.jpg)
Induction hypothesis: Assume, for an arbitrary *n* > 0 and *n* a power of 2, that
![](https://box.kancloud.cn/3fa60e45e2d575d1f3aeabc3128773e4_81x23.jpg)
Induction step: We need to show that
![](https://box.kancloud.cn/c301dd318e1c20313e5904ec77655d7f_103x23.jpg)
If we insert 2*n* in the recurrence, we get
![](https://box.kancloud.cn/97cbd1cdb67681d91af49ee45fc55019_400x22.jpg)
This completes the induction proof. Finally, because
![](https://box.kancloud.cn/7ffa104c1134a7cbd06c329669f085ec_96x23.jpg)
the solution to this recurrence is usually given as
![](https://box.kancloud.cn/c7b97800fb48193822b421005d67381d_141x23.jpg)
**![End example](https://box.kancloud.cn/e95df9d604ab2d89febe370ae4d88fb1_1x1.gif)**
Example B.3**![Start example](https://box.kancloud.cn/e95df9d604ab2d89febe370ae4d88fb1_1x1.gif)**Consider the recurrence
![](https://box.kancloud.cn/abc983b3debcedfec1e32623a6daad78_400x69.jpg)
The first few values are
![](https://box.kancloud.cn/cbf20e174baf224c79d64a9da13a5fe3_293x103.jpg)
There is no obvious candidate solution suggested by these values. As mentioned earlier, induction can only verify that a solution is correct. Because we have no candidate solution, we cannot use induction to solve this recurrence. However, it can be solved using the technique discussed in the next section.
**![End example](https://box.kancloud.cn/e95df9d604ab2d89febe370ae4d88fb1_1x1.gif)**
- Table of Contents
- BackCover
- Foundations of Algorithms Using C++ Pseudocode, Third Edition
- Preface
- Chapter Contents
- Pedagogy
- Course Outlines
- Acknowledgments
- Errors
- Chapter 1: Algorithms - Efficiency, Analysis, and Order
- 1.2 The Importance of Developing Efficient Algorithms
- 1.3 Analysis of Algorithms
- 1.4 Order
- 1.5 Outline of This Book
- Exercises
- Chapter 2: Divide-and-Conquer
- 2.1 Binary Search
- 2.2 Mergesort
- 2.3 The Divide-and-Conquer Approach
- 2.4 Quicksort (Partition Exchange Sort)
- 2.5 Strassen's Matrix Multiplication Algorithm
- 2.6 Arithmetic with Large Integers
- 2.7 Determining Thresholds
- 2.8 When Not to Use Divide-and-Conquer
- Exercises
- Chapter 3: Dynamic Programming
- 3.1 The Binomial Coefficient
- 3.2 Floyd's Algorithm for Shortest Paths
- 3.3 Dynamic Programming and Optimization Problems
- 3.4 Chained Matrix Multiplication
- 3.5 Optimal Binary Search Trees
- 3.6 The Traveling Salesperson Problem
- Exercises
- Chapter 4: The Greedy Approach
- 4.1 Minimum Spanning Trees
- 4.2 Dijkstra's Algorithm for Single-Source Shortest Paths
- 4.3 Scheduling
- 4.4 Huffman Code
- 4.5 The Greedy Approach versus Dynamic Programming: The Knapsack Problem
- Exercises
- Chapter 5: Backtracking
- 5.2 The n-Queens Problem
- 5.3 Using a Monte Carlo Algorithm to Estimate the Efficiency of a Backtracking Algorithm
- 5.4 The Sum-of-Subsets Problem
- 5.5 Graph Coloring
- 5.6 The Hamiltonian Circuits Problem
- 5.7 The 0-1 Knapsack Problem
- Exercises
- Chapter 6: Branch-and-Bound
- 6.1 Illustrating Branch-and-Bound with the 0 - 1 Knapsack problem
- 6.2 The Traveling Salesperson Problem
- 6.3 Abductive Inference (Diagnosis)
- Exercises
- Chapter 7: Introduction to Computational Complexity - The Sorting Problem
- 7.2 Insertion Sort and Selection Sort
- 7.3 Lower Bounds for Algorithms that Remove at Most One Inversion per Comparison
- 7.4 Mergesort Revisited
- 7.5 Quicksort Revisited
- 7.6 Heapsort
- 7.6.1 Heaps and Basic Heap Routines
- 7.6.2 An Implementation of Heapsort
- 7.7 Comparison of Mergesort, Quicksort, and Heapsort
- 7.8 Lower Bounds for Sorting Only by Comparison of Keys
- 7.8.1 Decision Trees for Sorting Algorithms
- 7.8.2 Lower Bounds for Worst-Case Behavior
- 7.8.3 Lower Bounds for Average-Case Behavior
- 7.9 Sorting by Distribution (Radix Sort)
- Exercises
- Chapter 8: More Computational Complexity - The Searching Problem
- 8.1 Lower Bounds for Searching Only by Comparisons of Keys
- 8.2 Interpolation Search
- 8.3 Searching in Trees
- 8.4 Hashing
- 8.5 The Selection Problem: Introduction to Adversary Arguments
- Exercises
- Chapter 9: Computational Complexity and Interactability - An Introduction to the Theory of NP
- 9.2 Input Size Revisited
- 9.3 The Three General Problem Categories
- 9.4 The Theory of NP
- 9.5 Handling NP-Hard Problems
- Exercises
- Chapter 10: Number-Theoretic Algorithms
- 10.1 Number Theory Review
- 10.2 Computing the Greatest Common Divisor
- 10.3 Modular Arithmetic Review
- 10.4 Solving Modular Linear Equations
- 10.5 Computing Modular Powers
- 10.6 Finding Large Prime Numbers
- 10.7 The RSA Public-Key Cryptosystem
- Exercises
- Chapter 11: Introduction to Parallel Algorithms
- 11.1 Parallel Architectures
- 11.2 The PRAM Model
- Exercises
- Appendix A: Review of Necessary Mathematics
- A.2 Functions
- A.3 Mathematical Induction
- A.4 Theorems and Lemmas
- A.5 Logarithms
- A.6 Sets
- A.7 Permutations and Combinations
- A.8 Probability
- Exercises
- Appendix B: Solving Recurrence Equations - With Applications to Analysis of Recursive Algorithms
- B.2 Solving Recurrences Using the Characteristic Equation
- B.3 Solving Recurrences by Substitution
- B.4 Extending Results for n, a Power of a Positive Constant b, to n in General
- B.5 Proofs of Theorems
- Exercises
- Appendix C: Data Structures for Disjoint Sets
- References
- Index
- Index_B
- Index_C
- Index_D
- Index_E
- Index_F
- Index_G
- Index_H
- Index_I
- Index_J
- Index_K
- Index_L
- Index_M
- Index_N
- Index_O
- Index_P
- Index_Q
- Index_R
- Index_S
- Index_T
- Index_U
- Index_V
- Index_W-X
- Index_Y
- Index_Z
- List of Figures
- List of Tables
- List of Algorithms, Examples, and Theorems
- List of Sidebars