Substitution method – Swati Varma's Notes

Solving recurrence relation using Substitution method

Express the Recursive Sequence
Write down the primary recurrence relation equation given by the algorithm.
Successively Substitute Lower Terms
Calculate what the relation looks like for its sub-components (e.g., if you have T(n-1), figure out what T(n-1) evaluates to by evaluating the original function at n-1) and substitute that expression back into the main equation.
Generalize the k-th Iteration Step
Repeat the substitution 3 to 4 times until a clear mathematical pattern emerges, then write a generalized formula representing the expression after k recursive steps.
Solve for the Base Case
Set the input size expression equal to the algorithm’s base case trigger value (often 1 or 0), isolate k, substitute k back into the generalized formula, and evaluate the final closed-form expression

Example 1:

Consider the recurrence relation:

T(n) = T(n/2) + c, if n > 1

T(n) = 1, if n = 1

Solution:

We start with:

T(n) = T(n/2) + c → (1)

If we put n = n/2 instead of n:

T(n/2) = T(n/4) + c → (2)

If we put n = n/4 instead of n:

T(n/4) = T(n/8) + c → (3)

Let us start with back substitution. Starting with equation (1), replace T(n/2) using equation (2):

T(n) = [T(n/4) + c] + c

T(n) = T(n/2²) + 2c

Now replace T(n/4) using equation (3):

T(n) = [T(n/8) + c] + 2c

T(n) = T(n/2³) + 3c

For the next iteration it will be:

T(n) = T(n/2⁴) + 4c

⋮

After k iterations:

T(n) = T(n/2ᵏ) + k · c

Now we wish to reach the termination condition, i.e.

T(n) = 1, if n = 1

Now, how do we get n = 1?

Let: n = 2ᵏ

From the recurrence obtained after k iterations:

T(n) = T(n/2ᵏ) + kC

Since n = 2ᵏ:

T(n) = T(n/n) + kC

∴ T(n) = T(1) + kC

Since T(1) = 1:

∴ T(n) = 1 + kC

Finding the value of k

We need to express k in terms of n because we need the time complexity in terms of n.

We know:

n = 2ᵏ

Taking logarithm on both sides:

log n = log 2ᵏ

log n = k log₂ 2

Since log₂ 2 is a constant:

k = log n

Therefore:

∴ T(n) = 1 + (log n) · C

Since 1 and C are constants:

∴ Complexity = O(log n)

Example 2:

Consider the recurrence relation:

T(n) = 1, if n = 1

T(n) = T(n − 1) + log n, if n > 1

Step 1: Expand the recurrence relation

Let n = n − 1

T(n − 1) = T(n − 1 − 1) + log(n − 1)

T(n − 1) = T(n − 2) + log(n − 1) → (2)

Similarly:

T(n − 2) = T(n − 3) + log(n − 2) → (3)

Back Substitution

Starting with:

T(n) = T(n − 1) + log n

Substitute T(n − 1):

T(n) = T(n − 2) + log(n − 1) + log n

Substitute T(n − 2):

T(n) = T(n − 3) + log(n − 2) + log(n − 1) + log n

Continuing in the same manner:

T(n) = T(n − 4) + log(n − 3) + log(n − 2) + log(n − 1) + log n

Run it k times

After k iterations:

T(n) = T(n − k) + log(n − (k − 1)) + log(n − (k − 2)) + log(n − (k − 3)) + … + log n

Reaching the termination condition

We need to reach the termination condition:

T(n) = 1, when n = 1

Therefore:

n − k = 1

k = n − 1

Substitute the value of k

Putting k = n − 1:

T(n) = T(n − (n − 1)) + log(n − (n − 1)) + log(n − (n − 2)) + log(n − (n − 3)) + … + log n

Therefore:

T(n) = T(1) + log 1 + log 2 + log 3 + … + log n

Since T(1) = 1:

T(n) = 1 + log 1 + log 2 + log 3 + … + log n

= 1 + log(1 · 2 · 3 · … · n)

= 1 + log(n!)

Simplifying n!

We know:

n! = n · (n − 1)!

= n · (n − 1) · (n − 2) · (n − 3) · … · 1

Since every factor is less than or equal to n:

n! ≤ nⁿ

Therefore:

1 + log(nⁿ)

Using the logarithm property:

log(nⁿ) = n log n

Therefore, complexity is:

1 + n log n

Ignoring constants and lower-order terms:

∴ Time Complexity = O(n log n)