Presented explicitly as a non-rigorous argument first, to expose the mechanism, with the fixes deferred (55:10, 55:52).

Definitions

  • B_i = number of bins with load at least i (57:05).
  • H(x) (capital, since g/h are taken) = the height of item x: x is the H(x)-th item inserted into its bin (57:41).
  • The non-rigorous step: pretend B_i is a fixed number rather than a random variable (57:05, 57:41).

The squaring recurrence

  • B_{i+1} ≤ #{x : H(x) ≥ i + 1} (58:42).
  • For x to reach height ≥ i + 1, both of its bins must already hold load ≥ i (59:58).
  • g and h are independent, so Pr[H(x) ≥ i+1] ≤ (B_i / n)² (1:00:41).
  • Summing over n items: B_{i+1} ≤ n · (B_i / n)², i.e.
B_{i+1}/n ≤ (B_i/n)²

(1:00:41, 1:01:44)

Why that gives log log n

  • Once B_i/n < 1/2, the fraction of heavy bins squares at every level (1:02:19).
  • Suppose B_10/n ≤ 1/2. Then B_{10+j}/n ≤ (1/2)^{2^j} (1:02:19, 1:02:57).
  • Done when the count drops below 1 bin, i.e. B_{10+j}/n < 1/n — which needs 2^j ≥ n, i.e. j ≥ log log n (1:03:33, 1:04:09).
flowchart LR
    A["B_i/n ≤ 1/2 at some constant level i"] --> B["each level squares the fraction"]
    B --> C["(1/2)^(2^j) after j more levels"]
    C --> D["fraction < 1/n means zero bins"]
    D --> E["j = log log n levels"]
  • The whole result is doubly-exponential decay driven by the independence of the two hash functions — that is the entire idea; everything that follows is making it rigorous (1:04:09, 1:04:44).
  • What is illegitimate: B_i is random and cannot be assumed to equal its expectation; the real proof must show a good event holds with high probability at every level (1:04:09, 1:04:44).