Class 19: Lower bounds on Sorting


Reading
Sections 8.1 of Introduction to Algorithms. This page provides several divide & conquer examples including that of integer multiplication due to Karatsuba. The same technique is used with matrix multiplication, and that algorithm is due to Strassen. Karatsuba discovered his method in the early 1960's. This link offers one comparison of Karatsuba and the grade school method.

Homework
None.

Lower Bounds on Sorting
We went through a proof that no comparison-based sorting algorithm can have a better worst-case than Θ(n lg n). In otherwords, anoy comparison-based sorting algorithm has a worst-case time comlexity that is Ω(n lg n). Sections 8.1 of Introduction to Algorithms discusses this as well.


Christopher W Brown
Last modified: Tue Mar 22 22:49:21 EST 2005