Uniform distribution modulo one and binary search trees (Q558117)

Sorting a sequence \(x=(x_k)\) of distinct numbers from \([0,1]\) by Quicksort generates a binary tree. Let \(H_n(x)\) denote the height of the tree generated by the prefix \(x_1,\dots,x_n\) of length \(n\) of \(x\). In the present paper it is shown that, if \(x\) is uniformly distributed in \([0,1]\), then \(H_n(x)=o(n)\) as \(n\to \infty\).