Type 1 Divide and Conquer Recurrence Relations
Following are some of the examples of recurrence relations based on divide and conquer.
T(n) = 2T(n/2) + cn
T(n) = 2T(n/2) + √n
These types of recurrence relations can be easily solved using Master Method
For recurrence relation T(n) = 2T(n/2) + cn, the values of a = 2, b = 2 and k =1. Here logb(a) = log2(2) = 1 = k. Therefore, the complexity will be Θ(nlog2(n)). Similarly for recurrence relation T(n) = 2T(n/2) + √n, the values of a = 2, b = 2 and k =1/2. Here logb(a) = log2(2) = 1 > k. Therefore, the complexity will be Θ(n).
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).