From charlesreid1

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