Algorithm Analysis/Merge Sort

Master Theorem Analysis

Merge sort has the recurrence relation:

$ T(n) = 2 T \left( \frac{n}{2} \right) + f(n) $

due to the fact that each split operation splits the array of data into 2 parts of size $ \frac{n}{2} $.

The work done merging (the f(n) on the right) is linear, so $ f(n) = O(n) $.

Now we can apply the Master Theorem. The quantity c is:

$ c = \log_b{(a)} = \log_2{(2)} = 1 $

Therefore $ O(n^c) = O(n) $

If we examine the 3 cases, we can see that we fall into Case 2:

$ f(n) = \Theta \left( n^{\log_b{(a)}} \log^{k}{(x)} \right) $

with k = 0. Then that implies:

$ T(n) = \Theta(n \log^{k+1}{(n)}) $

Therefore, overall, merge sort is Theta(n log n):

$ T(n) = \Theta( n \log{n} ) $