Limitations of Substitution method
The Substitution method is a useful technique to solve recurrence relations, but it also has some limitations. Some of the limitations are:
- It is not guaranteed that we will find the solution as substitution method is based on guesses.
- It doesn’t provide guidance on how to make an accurate guess, often relying on intuition or trial and error.
- It may only yield a specific or approximate solution rather than the most general or precise one.
- The substitution method isn’t universally applicable to all recurrence relations, especially those with complex or variable forms that do not get simplified using substitution.
Substitution Method to solve Recurrence Relations
Recursion is a method to solve a problem where the solution depends on solutions to smaller subproblems of the same problem. Recursive functions (function calling itself) are used to solve problems based on Recursion. The main challenge with recursion is to find the time complexity of the Recursive function. In this article, we will learn about how to find the time complexity of Recursive functions using Substitution Method.