Merge Sort Analysis

Discrete Math · Axiom Academy

Solve T(n) = 2T(n/2) + n using substitution and master theorem to verify O(n log n) complexity Comparing Sorting Algorithm Complexities Now that we've proven Merge Sort has O(n log n) complexity, let's compare it with other sorting algorithms: Excellent work! You've successfully analyzed Merge Sort's complexity. Here's what we learned: Recurrence Relations: T(n) = 2T(n/2) + n models divide-and-conquer algorithms that split problems in half Substitution Method: Repeatedly expanding terms reveals patterns that lead to the general solution Logarithmic Depth: Dividing by 2 each time creates log₂(n) levels in the recursion tree Master Theorem Verification: For T(n) = aT(n/b) + f(n), we have a=2, b=2, f(n)=n. Since f(n) = Θ(n log b a ) = Θ(n), Case 2 applies, giving T(n) = Θ(n log n) Consistent Performance: Merge Sort achieves O(n log n) in best, average, and worst cases—unlike Quick Sort's O(n²) worst case Trade-off: The price for guaranteed performance is O(n) extra space for the merge operation This analysis technique applies to many divide-and-conquer algorithms! You'll use similar approaches for analyzing binary search trees, recursive matrix multiplication, and other important algorithms.

This is the written version of the interactive lesson above. See the full Discrete Math course.