Substitution method for solving recurrences

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(2ⁿ). 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 * 2ⁿ - 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(2ⁿ).

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!