The first method is Substitution Method.
The substitution method comprises 3 steps
- Guess the form of the solution
- Verify by Induction
- Solve for constants.
We substitute the guessed solution for the function when applying the inductive hypothesis to smaller values. Hence the name “Substitution Method.”
This method is powerful, but we must be able to guess the form of the answer in order to apply it. Our guessed solution must provide an upper bound on the algorithm’s time complexity. If the algorithm’s time complexity is n, we must come up with a guessed solution that is O(n) or greater, such as O(n*logn) or O(n2), which is an upper bound of O(n).
If we are experienced in solving recurrence problems, then the substitution method can help, but if we are not, then it will make no sense to apply it.
Example:
(1) T(n) = T(n/2) + n
Also, we have T(1) = 1
Ans-
1st Try
Step 1: Guess the form of the solution
T(n) = T(n/2) + n ….(1)
Let’s suppose the time complexity of this problem is O(log n), for n ≥ 2.
For n = 1, T(1) = 0, which is not the case.
Step 2: Verify the induction
We need to prove that T(n) = c*log n (c is constant)
Equation (1) is T(n) = T(n/2) + n
=> T(n) <= c*log(n/2) + n
=> T(n) <= c*log(n) – c*log 2 + n
[Remove c*log 2 as this is a constant]
=> T(n) <= c*log(n) + n
=> T(n) = O(n)
So, Induction failed. O(log n) is not an upper bound of O(n).
2nd Try
Step 1: Guess the form of the solution
T(n) = T(n/2) + n ….(1)
Let’s suppose the time complexity of this problem is O(n). I think this will be the upper bound of the given algorithm.
Step 2: Verify the induction
We need to prove that T(n) = c*n (c is constant)
Equation (1) is T(n) = T(n/2) + n
=> T(n) <= c*n/2 + n
=> T(n) <= c1*n
=> T(n) = O(n)
Induction Verified.
Step 3: Solve for constants
c*n/2 + n => 0
if n => 1
and c => 1, then there is no negative term
Then, finally T(n) is O(n). This solution is the upper-bound of the time complexity of the given algorithm.
Example:
(1) T(n) = 4T(n/2) + n
Also, we have T(1) = 1
Ans-
Step 1: Guess the form of the solution
T(n) = 4T(n/2) + n ….(1)
Experienced Thinking – if the variable form (n) is divided by 2 then most of the time log n comes in the result. Also, the running time, f(n) is n, so my sixth sense says that the result will not be lesser than (n log n), but in the compiling time, it is 4T(n/2). 4 is very greater than 2 so the result will be not lesser than O(n2). I am sure that the answer will be in n2 form.
=> T(n) = O(n2) (we guessed)
Step 2: Verify the induction
We need to prove that T(n) = c*n2 (c is constant)
Equation (1) is T(n) = 4T(n/2) + n
=> T(n) <= 4c*(n/2)2 + n
=> T(n) <= c*n2 + n
=> T(n) <= c*n2
Here, n2 will be always positive. So, what I assumed was true.
Step 3: Solve for constants
c* n2 + n => 0
if n => 1
and c => 1, then there is no negative term
Then, finally T(n) is O(n2). This solution is the upper-bound of the time complexity of the given algorithm.
Test Yourself
Q1- Explain the three steps involved in the Substitution Method for solving recurrence relations.
The Substitution Method for solving recurrence relations comprises three steps:
- Guess the form of the solution: In this step, we make an educated guess about the form of the solution based on the recurrence relation’s structure. The guessed solution should provide an upper bound on the algorithm’s time complexity.
- Verify by Induction: Once we have guessed the form of the solution, we need to verify whether the guess is correct or not. This is done through mathematical induction, where we assume the guess holds for all smaller values and then prove it for the given recurrence relation.
- Solve for constants: After verifying the guess by induction, we need to find the constants involved in the solution. This involves solving any constant factors and boundary conditions to get the final time complexity.
Q2- Why is it important for the guessed solution in the Substitution Method to provide an upper bound on the algorithm’s time complexity?
The guessed solution in the Substitution Method needs to provide an upper bound on the algorithm’s time complexity because we are interested in finding the worst-case time complexity of the algorithm. An upper bound represents the maximum time the algorithm will take to execute for any input size n. If the guessed solution is not an upper bound, it may not accurately reflect the algorithm’s worst-case behavior, leading to incorrect analysis.
Q3- Discuss the significance of the Substitution Method in analyzing the time complexity of algorithms.
The Substitution Method is a powerful tool for analyzing the time complexity of algorithms, especially for solving recurrence relations. It provides a systematic approach to find the upper bound on the time complexity of an algorithm. By making an educated guess about the form of the solution, we can quickly narrow down the possible time complexities and focus on finding the correct upper bound.
Moreover, the Substitution Method helps us understand how the algorithm’s time complexity grows with the input size. It allows us to identify the dominating term in the recurrence relation, which gives us insights into the algorithm’s scalability and efficiency.
