Articles / DAA · Part 4

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.

Complexity Analysis Techniques: Substitution Method and Recursion Tree Method

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:

  1. Substitution Method
  2. Recursion Tree Method

2. Substitution Method

The Substitution Method involves three main steps:

  1. Guess the solution based on the recurrence or previous knowledge.
  2. Substitute the guess into the recurrence.
  3. 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 questions
What is the main idea of the Substitution Method?
What does each node in a recursion tree represent?
For \(T(n)=2T(n/2)+n\), how much total work is performed at each level?
How many levels of division are there in \(T(n)=T(n/2)+1\)?
What is the complexity of \(T(n)=2T(n/2)+n\)?

Keep a copy

Read offline as a printout or PDF.

farhanpaal.com

Keep reading

DAA · Part 1

What is DESIGN AND ANALYSIS OF ALGORITHM?

What is Design and Analysis of Algorithms (DAA)? Explore how algorithms are designed, analyzed for efficiency and correctness, and what this DAA…

6 min read

Ask Farhan

Ask anything about Farhan