Algorithm Analysis/Merge Sort

Master Theorem Analysis

Merge sort has the recurrence relation:

$T(n)=2T\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})$