Divide and Conquer - Mergesort (6/7)

In this lecture, we finish analyzing mergesort's running time for arbitrary input sizes. We begin with a quiz about the exact solution to the recurrence, exploring why the formula for powers of two does not apply directly to every integer n. We then use strong induction to prove an upper bound of T(n) less than or equal to n * ceiling of log n. This will show that uneven splits and rounding do not change the overall result. Mergesort runs in O(n log n) time for any input size, not just powers of two.