On the Variance of the Height of Random Binary Search Trees

Let Hₙ be the height of a random binary search tree on n nodes. We show that there exists a constant α = 4.31107 … such that P \|Hₙ - α log n| > β log log n\ → 0, where β > 15 α/ln 2 = 93.2933 …. The proof uses the second moment method and does not rely on properties of branching processes. We also show that Varₙ\ = O((loglog n)²).