Average-case analysis of QuickSort and Binary Insertion Tree height using incompressibility |
| |
| Authors: | Brendan Lucier Tao Jiang Ming Li |
| |
| Affiliation: | a Department of Computer Science, University of Waterloo, Waterloo, Ont. N2L 3G1, Canada
b Department of Compute Science, University of California, Riverside, CA 92521, USA |
| |
| 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. |
| |
| Keywords: | Analysis of algorithms Binary insertion trees Incompressibility Kolmogorov complexity QuickSort |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
