Type 3 Value Substitution Before Solving
Sometimes, recurrence relations can’t be directly solved using techniques like substitution, recurrence tree or master method. Therefore, we need to convert the recurrence relation into appropriate form before solving. For example,
T(n) = T(√n) + 1
To solve this type of recurrence, substitute n = 2^m as:
T(2^m) = T(2^m /2) + 1
Let T(2^m) = S(m),
S(m) = S(m/2) + 1
Solving by master method, we get
S(m) = Θ(logm)
As n = 2^m or m = log2(n),
T(n) = T(2^m) = S(m) = Θ(logm) = Θ(loglogn)
Different types of recurrence relations and their solutions
In this article, we will see how we can solve different types of recurrence relations using different approaches. Before understanding this article, you should have idea about recurrence relations and different method to solve them (See : Worst, Average and Best Cases, Asymptotic Notations, Analysis of Loops).