CSE201, Winter 2025, Lec 13: Divide and conquer, Karatsuba integer multiplication
C. Seshadhri · 88:05
Merge sort's T(n) = 2T(n/2) + O(n) recurrence gives O(n log n) because work stays constant per level — but the naive divide-and-conquer for integer multiplication gives T(n) = 4T(n/2) + O(n), where work *grows* 2× per...