Analyzing the Merge Sort Algorithm
- This analysis generalizes to the formula
- Since we assumed n =
2m we have
- To establish growth order, we drop the lower order term and the constant factor.
- The change of base formula for logarithms
allows us to drop the base of the logarithm.
- Hence merge sort is an O(n log n) algorithm.