Combinatorics

Lower bounds by playing against the algorithm: finding max and second-max needs n + ceil(log n) - 2 comparisons.

A decision tree with n! leaves must be log(n!) deep, and log(n!) = Theta(n log n) by the (n/2)^(n/2) trick — the one step that costs this post its L1.

Any algorithm that shrinks some inputs must grow others. Kills every "compresses random data" claim on sight.

n+1 items, n boxes, one collision. The cheapest impossibility argument in existence, and the seed for No universal lossless compressor and The birthday bound.