Divide and Conquer - Mergesort (5/7)

We prove that mergesort runs in O(n log n) time using induction. Starting with the base case, we show how the recurrence lets us prove the result for a problem of size 2n, assuming it holds for size n. Along the way, we use a logarithm property to simplify the algebra and establish the result for input sizes that are powers of two. A recursion tree helps us understand why a result is true but induction lets us prove it rigorously.