Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Substitution Method
3.
Examples of the process of solving recurrences using substitution
4.
FAQs
5.
Key Takeaways
Last Updated: Mar 27, 2024

Substitution method for solving recurrences

Author SHIKHAR SONI
2 upvotes
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Introduction

Recurrence relations are equations that describe themselves. We encounter recurrences in various situations when we have to obtain the asymptotic bound on the number of O(1) operations (constant time operations, ones that aren't affected by the size of the input) performed by that recursive function. It's essential to have tools to solve these recurrences for time complexity analysis, and here the substitution method comes into the picture.

Substitution Method

In the substitution method, we have a known recurrence, and we use induction to prove that our guess is a good bound for the recurrence's solution. This method works well in providing us with a good upper bound in most recurrences that can't be solved using the Master's Theorem or other more straightforward ways.

Practising similar questions is essential if we try to make a guess that'll probably work for us. We'll cover some examples to get you started in the next section.

The steps to use the Substitution method are as follows.

  1. Guess a solution through your experience.
  2. Use induction to prove that the guess is an upper bound solution for the given recurrence relation. 

Also see, Longest Common Substring and Data Structure

Must Read Recursion in Data Structure

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Examples of the process of solving recurrences using substitution

Let’s say we have the recurrence relation given below.

T(n) = 2 * T(n-1) + c1, (n > 1)
T(1) = 1

We know that the answer is probably T(N) = O(2n). The observation that we are almost doubling the number of O(1) operations for a constant decrease in n leads to the guess. We will thus show that T(n) <= k * 2n - b and prove our answer.

Now we come over to the use of induction, here the base case occurs when n=1.

=> T(1) = 1 <= k * 21 - b = 2 * k - b.
=> 2 * k - b >= 1
=> k >= (b+1)/2

 

Inductive step: We assume that the property that we guessed holds for n - 1 and prove that in such a case it will also hold for n.

=> T(n) = 2 * (T(n-1)) + c1
=> T(n) <= 2 * (k * 2n-1 - b) + c1
=> T(n) <= k * 2n - 2 * b + c1
=> T(n) <= k * 2n - b (let, b = c1)

After the above steps we obtain, b = c1 and k = (b + 1) / 2. These equations have infinite solutions, and we are free to choose any constant as big-O notation doesn't care about constants being multiplied, divided, added or subtracted.

Hence, we have confirmed that T(n) = O(2n).

 

Let's cover another example. The recurrence relation is described below.

T(n) = 2 * T(n / 2) + n, n > 1
T(1) = 1

T(n) = O(nlog(n)) is our guess. We must therefore show that T(n) <= c1nlog(n) + c2 to prove our guess.

Base case (n = 1)

=> T(1) = 1 <= c1 * 1 * log(1) + c2
=> 1 < = c1 * 1 * 0 + c2
=> c2 >= 1

 

Inductive step, (n > 1)

=> T(n) <= 2 * T(n / 2) + n
=> T(n) <= 2 * (c1 * n / 2 * log(n / 2) + c2) + n
=> T(n) <= c1 * n * log(n) - c1 * n * log(2) + 2 * c2 + n
=> T(n) <= c1 * n * log(n) + (1 - c1 * log(2)) * n + 2 * c2

We can conclude that the above holds for some c1 >= 1 / log(2) and some c2. We again have numerous solutions for the above set of equations, and hence the guess is accurate and T(n) = O(n * log(n)).

 

Also see, Morris Traversal for Inorder and Rabin Karp Algorithm

FAQs

1. What are recurrences and their uses?
A recurrence can describe any sequence of elements in an array in terms of themselves. Recurrences are used in various branches of mathematics in addition to Computer Science (in time complexity analysis) their application in finding the bound for the number of trivial operations by an algorithm, such as Number Theory (Fibonacci sequence), Calculus (Euler's Theorem), etc.

An example of a recurrence,

T(N) = T(N/2) + 1, (n > 1)
T(1) = 1

 

2. Why should we learn about different methods for solving recurrences?
Many methods make it easier for us to solve particular problems. Depending on the requirement, they can also help us (depending on if we need a tight bound or just an upper bound), and there are recurrences where you may not apply specific methods.

For example, Master’s Theorem can’t solve recurrences if in the recurrence T(n) = a * T(n / b) + f(n), f(n) is not a polynomial.
 

3. What is induction and its uses?
It's a proving method, generally used to prove that a statement is true for all natural numbers. The key idea is to establish the base case and then prove that if a statement is true, the next one also has to be true. It's used as a tool to prove various statements in mathematics and computer science, such as the sum of all natural numbers S(n) = (n * (n + 1)) / 2.
 

4. What is Master's Theorem?
It's another method to solve recurrences. It covers many common recurrences that generally appear in many "divide and conquer" algorithms and provides a complete and straightforward way for solving such recurrences. Its usage, however, has limitations and can't always be used.
 

5. Where we shouldn't use the Substitution Method?
Let's say we have recurrences that satisfies all the requirements for master's theorem. Then it's best to use it. Methods that provide a definite answer easily and don't require guessing are usually faster and need much less work to give even a tight bound for our recurrence using master's theorem, unlike the substitution method.

Key Takeaways

This article covers substitution, one of the methods to find a bound on a recurrence. Other methods to achieve similar objectives are Iteration, Recursion Tree and Master's Theorem. To understand the blog better, refer to the article here about Understanding of Analysis of Algorithms and here about Master's Theorem.

Also check out - Rod Cutting Problem

Learn more about the C++ STL library from here if you have trouble understanding some part of the code. Visit the link here for carefully crafted courses on campus placement and interview preparation on coding ninjas.

Happy learning!

Previous article
Trick questions from Time & Space Complexity
Next article
Iteration Method
Live masterclass