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