Uniform distribution modulo one and binary search trees (Q558117)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Uniform distribution modulo one and binary search trees |
scientific article; zbMATH DE number 2184591
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Uniform distribution modulo one and binary search trees |
scientific article; zbMATH DE number 2184591 |
Statements
Uniform distribution modulo one and binary search trees (English)
0 references
30 June 2005
0 references
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\).
0 references
uniform distribution
0 references
binary search trees
0 references
