| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 428806 | Information Processing Letters | 2007 | 7 Pages |
Abstract
We study the Kolmogorov complexity of a Binary Insertion Tree, and present a succinct encoding scheme for Binary Insertion Trees produced from incompressible permutations. Based on the encoding scheme, we obtain a simple incompressibility argument that yields an asymptotic analysis of the average height of a Binary Insertion Tree. This argument further implies that the QuickSort algorithm sorts a permutation of n elements in Θ(nlgn) comparisons on average.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
