Advanced Search

Any sequence $x={\left(x_k\right)}_{k=1}^{\infty }$ of distinct numbers from [0,1] generates a binary tree by storing the numbers consecutively at the nodes according to a left-right algorithm (or equivalently by sorting the numbers according to the Quicksort algorithm). Let $H_n\left(x\right)$ be the height of the tree generated by $x_1,\cdots ,x_n.$ Obviously $$\frac{logn}{log2}-1\le H_n\left(x\right)\le n-1.$$ If the sequences $x$ are generated by independent random variables having the uniform distribution on [0, 1], then it is well known that there exists $c$ > $0$ such that $H_n\left(x\right)\sim clogn$ as $n\to \infty$ for...