# Algorithm Analysis/Merge Sort

### 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:

Therefore

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):

# Flags

AlgorithmsSeries on Algorithms
Algorithms/Sort Three solid O(n log n) search algorithms: Merge Sort Algorithm Analysis/Merge Sort
Algorithms/Search
Algorithms/Combinatorics
Algorithms/Strings
Algorithm complexity Amortization Algorithm Analysis/Matrix Multiplication
Estimation
Project Euler
· Template:AlgorithmsFlag · e |