B.log

Random notes mostly on Machine Learning

On Sorting Complexity

It’s well known that lower bound for sorting problem (in general case) is \(\Omega(n \log n)\). The proof I was taught is somewhat involved and is based on paths in “decision” trees. Recently I’ve discovered an information-theoretic approach (or reformulation) to that proof.