From charlesreid1

Master Theorem Analysis

Merge sort has the recurrence relation:

due to the fact that each split operation splits the array of data into 2 parts of size .

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

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


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

with k = 0. Then that implies:

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