Complexity Analysis Techniques: Substitution Method and Recursion Tree Method
Learn how to solve recurrence relations using the Substitution Method and Recursion Tree Method, with step-by-step examples and complexity analysis.
1. Introduction
Recursive algorithms solve problems by breaking them into smaller problems of the same type.
For example, Merge Sort divides an array into two smaller halves, sorts them recursively, and then combines the results.
To analyze such algorithms, we often express their running time using a recurrence relation.
Consider:
\[
T(n)=2T\left(\frac n2\right)+n
\]
This means:
- The algorithm solves two subproblems, each of size \(n/2\).
- The additional work outside the recursive calls is \(n\).
But how do we determine the complexity of this recurrence?
Two commonly used techniques are:
- Substitution Method
- Recursion Tree Method
2. Substitution Method
The Substitution Method involves three main steps:
- Guess the solution based on the recurrence or previous knowledge.
- Substitute the guess into the recurrence.
- Prove that the guess holds using mathematical induction.
It is particularly useful when we already have an idea of the recurrence’s growth rate.
Example
Consider:
\[
T(n)=2T\left(\frac n2\right)+n
\]
We want to determine its asymptotic complexity.
Step 1: Guess the Solution
From the recurrence, the problem is divided into two halves, and the additional work is \(n\).
We guess:
\[
T(n)=O(n\log n)
\]
Now we need to verify this guess.
Step 2: Substitute the Guess
Assume that for smaller values of \(n\):
\[
T(n)\leq c\frac n2\log_2\left(\frac n2\right)
\]
Since there are two recursive calls:
\[
T(n)\leq
2\left(c\frac n2\log_2\left(\frac n2\right)\right)+n
\]
Simplifying:
\[
T(n)\leq cn\log_2\left(\frac n2\right)+n
\]
Using:
\[
\log_2\left(\frac n2\right)=\log_2n-1
\]
We get:
\[
T(n)\leq cn(\log_2n-1)+n
\]
\[
T(n)\leq cn\log_2n-cn+n
\]
\[
T(n)\leq cn\log_2n-(c-1)n
\]
For \(c\geq1\):
\[
T(n)\leq cn\log_2n
\]
Thus, the upper-bound guess holds for an appropriate constant (c), with the base case handled separately.
Step 3: Conclude
We have established an upper bound:
\[
T(n)=O(n\log n)
\]
The recurrence also performs at least \(n\) work at each recursive level, and its recursion tree has \(\log_2n\) levels. Therefore, the total work is at least proportional to \(n\log n\).
Hence:
\[
\boxed{T(n)=\Theta(n\log n)}
\]
The Substitution Method is called this because we substitute our assumed bound into the recurrence and use induction to verify it.
3. Recursion Tree Method
The Recursion Tree Method represents a recurrence as a tree.
Each node represents the work performed by a recursive call. The tree helps us visualize:
- How many recursive calls are generated.
- The size of each subproblem.
- The work performed at each level.
- The total work across all levels.
We then add the work performed at every level to determine the overall complexity.
Example
Consider the same recurrence:
\[
T(n)=2T\left(\frac n2\right)+n
\]
Level 0 — Root
The original problem has size \(n\).
Its additional work is:
\[
n
\]
Level 1
The problem is divided into two subproblems of size \(n/2\).
Each contributes \(n/2\) work.
Total work:
\[
\frac n2+\frac n2=n
\]
Level 2
Each subproblem is divided again, producing four subproblems of size \(n/4\).
Total work:
\[
4\times\frac n4=n
\]
General Level
At level (i):
- Number of subproblems: \(2^i\)
- Size of each subproblem: \(n/2^i\)
- Work per subproblem: \(n/2^i\)
Therefore, the total work at that level is:
\[
2^i\times\frac n{2^i}=n
\]
Every level contributes (n) work.
Number of Levels
The problem keeps dividing by 2 until the subproblem size becomes 1.
\[
\frac n{2^k}=1
\]
Therefore:
\[
2^k=n
\]
\[
k=\log_2n
\]
So the tree has approximately \(\log_2n\) levels of division.
Total Work
Since each level contributes (n) work and there are \(\log_2n\) levels:
\[
T(n)=n\log_2n
\]
The leaves contribute a total of \(\Theta(n)\), which does not change the overall growth.
Therefore:
\[
\boxed{T(n)=\Theta(n\log n)}
\]
4. Visualizing the Recursion Tree
For \(T(n)=2T(n/2)+n\):
Each level contributes a total of \(n\) work.
Level 0
\[
n
\]
↓ Level 1
\[
\frac n2+\frac n2=n
\]
↓ Level 2
\[
\frac n4+\frac n4+\frac n4+\frac n4=n
\]
↓ ⋮
Each level contributes \(n\).
↓ Last Level
\[
n\text{ leaves}\times\text{constant work}
\]
Total work:
\[
\underbrace{n+n+n+\cdots+n}_{\log_2n\text{ levels}}
\]
\[
\boxed{\Theta(n\log n)}
\]
5. Another Recursion Tree Example
Consider:
\[
T(n)=T\left(\frac n2\right)+1
\]
Here, each recursive call creates only one smaller subproblem, and each level performs constant additional work.
The problem sizes are:
\[
n,\frac n2,\frac n4,\frac n8,\ldots,1
\]
The number of levels is:
\[
\log_2n
\]
Since every level contributes constant work:
\[
T(n)=1+1+1+\cdots+1
\]
Therefore:
\[
\boxed{T(n)=\Theta(\log n)}
\]
This is the same growth pattern as Binary Search.
6. Comparison of Both Methods
| Substitution Method | Recursion Tree Method |
|---|---|
| Guesses a bound and proves it using induction | Visualizes recursive calls as a tree |
| More mathematical | More intuitive and visual |
| Useful for proving a guessed bound | Useful for understanding work at each level |
| Requires a suitable guess | Requires calculating level work and tree height |
Both methods can be used to analyze recursive algorithms. Sometimes the recursion tree helps us discover the answer, and the substitution method helps us prove it formally.
Recursive algorithms often produce recurrence relations that are not immediately easy to solve.
The Substitution Method helps us verify a complexity bound using mathematical induction, while the Recursion Tree Method helps us visualize recursive calls and calculate the work at each level.
Both techniques are valuable tools in algorithm analysis.
In the next article, we will study the Master Theorem, which provides a faster way to solve many divide-and-conquer recurrences without repeatedly expanding them or proving bounds through substitution.
Quick quiz
5 questionsOriginally published at farhanpaal.com — https://farhanpaal.com/articles/complexity-analysis-techniques-substitution-method-and-recursion-tree-method/
Keep a copy
Read offline as a printout or PDF.
farhanpaal.com