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} )$

Flags