Comparison sorting lower bound
Distinct-key comparisons need enough branches to distinguish orders.
Key knowledge
Sorting n distinct keys by binary comparisons has n! possible orders. Its decision tree therefore needs worst-case depth at least ⌈log₂(n!)⌉, which is Ω(n log n).
Conditions and scope
- The algorithm gains ordering information only through comparisons.
- Integer-key counting or radix methods use additional operations and are outside this lower bound.
Sources · 1
References
Sources retain their recorded scope. A source link alone does not establish verification of every statement.
Evidence and review
Physical page 2: comparison decision tree, n! outputs and Ω(n log n) lower bound; integer-key sorting uses another model.
2026-10-10 · Comparison decision-tree lower bound, Lecture 5.
Entry details
Permanent link to this entry ↗- Record identity
- info-comparison-sorting
- Revision
- university-reference.1
- Structured reference record
- University reference