The complexity of the complexity of merge sort.

Here I thought unwinding techniques was somewhat uneasy to absorb, far came the complexity of merge sort. There are essentially four steps involved in the quest of finding the complexity of merge sort.

Step 1: We have to unwind the inductive formula with special cases to come up with a non-inductive formula.

Step 2: We then using strong induction to prove that the non-inductive formula is correct for all the special cases.

Step 3: We prove the monotonicity of the inductive formula.

Step 4: We merge the monotonicity and the non-inductive formula to prove the complexity of merge sort.

This four steps are the core components of the master theorem for divide-and-conquer. I don’t particular enjoy rigorous proofs, but I find the idea of dividing a bigger and more complex problem into smaller and manageable problems enchanting.