The Mystery of Recurrence Relation

In this post I will introduce you to something called Recurrence Relation. And we will derive the running time of Merge Sort. So stay tuned because Winter is Coming.

Analyzing divide and conquer algorithms
When an algorithm contains a recursive call to itself, we often describe running time as recurrence equation or recurrence, which describes the overall running time on a problem size of n in terms of the running time of the running time on smaller inputs.
A recurrence for the running time of a divide-and-conquer algorithm falls out from the three steps of the basic paradigm. As before, we let T(n) be the running time on a problem size of n. If the problem size is small enough, say n<=c for some constant c, the straightforward solution takes Θ(1), 
constant time. Suppose our division of the problem yields "a" sub problems each of size 1/b of the original. It takes time T(n/b) to solve one sub problem of size n/b, so it would take a*T(n/b). If we take D(n) time to divide the problem into sub problems and C(n) time to combine the solutions to the sub problems to the original problem, we get the recurrence.

T(n) = {     Θ(1)                                    if n<=c
                 a*T(n/b)+D(n)+C(n)          otherwise

In case of Merge Sort b = 2 if we have even number of elements and a=2 that is we divide the problem into 2 sub problems. We get the recurrence solution as :

T(n) = {    Θ(1)                                    if n =1

                2*T(n/2) +cn                      if n>1

If we solve the above recurrence relation we would get T(n) = Θ(n logn)

You can find the solution to the recurrence relation using Masters Theorem but that won't help you to understand how we arrive at the solution Θ(n logn) . 

So lets derive the complexity of Merge Sort using Recursion Tree Method.

We consider the root of the tree to be c(n) which the size of the original array that needs to be sorted. Now that root is further sub-divided into two smaller sub trees, which gives the recurrences T(n/2) and T(n/2) respectively. Futher sub dividing the two sub trees we get four sub trees of T(n/4). We expanding until we reach the last level where the problem size becomes 1 which is the base condition in the merge_sort() function. Next, we add the cost across the each level of the tree. If you observe in the image above you will find that the root has the cost cn, the next level down has cost cn/2+cn/2 = cn, the level after that has cost cn/4+cn/4+cn/4+cn/4. In general the level i below the top has 2^i nodes each a cost of c(n/2^i) , so that the ith level below the top has total cost  2^i *c(n/2^i) that is = cn. The total number of levels of the recursion tree is lg n +1, where  n is the total number of leaves which represents the input size n. A tree with n = 2^(i+1) , so the number of levels will be lg 2^(i+1)+1. That was just an analysis you need not keep it in mind.

To compute the total cost you just need to add the cost of each level, as we have lg n+1 levels each costing cn, for a total cost of cn*(lg n +1) =  cn lgn + cn . Ignoring the lower order constant term c, we finally get our result T(n) = Θ(n logn). 

I hope I could explain it in the best way I could, if you have any questions. Please feel free to ask in the comments below.