HyperLogLog Estimates Vocabulary Size with 2.71% Error Using Only 4,096 Registers

Sorting, hashing, and sketches on 370,103 words

In this post, we put Python's core containers to the test on a real dataset: 370,103 unique English words. We sort them six ways, hash them into four structures, and sketch them with four probabilistic algorithms, tracking time and memory costs. The standout result: HyperLogLog estimates vocabulary size with just 2.71% error using only 4,096 registers. We also explore complexity analysis, showing how Big-O, Big-Theta, and amortized analysis predict real behavior, and implement classic sorts like quicksort from scratch.