# 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.