CS61B Textbook 2025
Ctrlk
  • Spring 2025 Textbook
  • Contributors
  • DISCLAIMER
  • 1. Introduction
  • 2. Defining and Using Classes
  • 3. References, Recursion, and Lists
  • 4. SLLists
  • 5. DLLists
  • 6. Arrays
  • 7. Testing
  • 8. ArrayList
  • 9. Inheritance I: Interface and Implementation Inheritance
  • 10. Inheritance II: Subtype Polymorphism, Comparators, Comparables, Generic Functions
  • 11. There is no chapter 11.
  • 12. Inheritance III: Iterators, Object Methods
  • 13. Asymptotics I
  • 14. Disjoint Sets
  • 15. Asymptotics II
  • 16. ADTs and BSTs
  • 17. B-Trees
  • 18. Red Black Trees
  • 19. Hashing I
  • 20. Hashing II
  • 21. Heaps and Priority Queues
  • 22. Tree Traversals and Graphs
  • 23. Graph Traversals and Implementations
  • 24. Shortest Paths
  • 25. Minimum Spanning Trees
  • 26. Prefix Operations and Tries
  • 27. Software Engineering I
  • 28. Reductions and Decomposition
  • 29. Basic Sorts
  • 30. Quicksort
  • 31. Software Engineering II
  • 32. More Quick Sort, Sorting Summary
  • 33. Software Engineering III
  • 34. Sorting and Algorithmic Bounds
    • 34.1 Sorting Summary
    • 34.2 Math Problems Out of Nowhere
    • 34.3 Theoretical Bounds on Sorting
    • 34.4 Summary
    • 34.5 Exercises
  • 35. Radix Sorts
  • 36. Sorting and Data Structures Conclusion
  • 37. Software Engineering IV
  • 38. Compression and Complexity
  • 39. Compression, Complexity, P = NP
Powered by GitBook
On this page

34. Sorting and Algorithmic Bounds

By William Lee and Angel Aldaco

34.1 Sorting Summary34.2 Math Problems Out of Nowhere34.3 Theoretical Bounds on Sorting34.4 Summary34.5 Exercises
Previous33.5 ExercisesNext34.1 Sorting Summary