MIT 6.006 Lecture 7: Decision-Tree Ω(n log n) Lower Bound, Counting Sort & Radix Sort
Proves the information-theoretic Ω(n log n) comparison-sorting barrier via Stirling's approximation on n!, then breaks through it in linear time using integer Radix Sort.
Theory & AlgosSystems & CSAlgorithms & Data StructuresProbability & Information TheoryLower BoundsRadix Sort
MIT 6.006 Introduction to Algorithms, Fall 2011
View the complete course: http://ocw.mit.edu/6-006F11
Instructor: Erik Demaine
More courses at http://ocw.mit.edu
Previous · Lecture 6
MIT 6.006 Lecture 6: AVL Trees, Tree Rotations & Guaranteed O(log n) Height
Next · Lecture 8MIT 6.006 Lecture 8: Hashing with Chaining, Simple Uniform Hashing & Universal Families
Comments
Add a comment...Sign in