Name
Title | ||
|---|---|---|
Average-case analysis of QuickSort and Binary Insertion Tree height using incompressibility |
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 @Q(nlgn) comparisons on average. |
Year | DOI | Venue |
|---|---|---|
2007 | 10.1016/j.ipl.2007.01.007 | Inf. Process. Lett. |
Keywords | Field | DocType |
average-case analysis,simple incompressibility argument,encoding scheme,quicksort algorithm sort,asymptotic analysis,binary insertion tree,kolmogorov complexity,incompressible permutation,succinct encoding scheme,average height,binary insertion trees,binary insertion tree height,analysis of algorithms | Discrete mathematics,Combinatorics,AVL tree,Self-balancing binary search tree,Binary tree,Quicksort,Order statistic tree,Red–black tree,Random binary tree,Binary expression tree,Mathematics | Journal |
Volume | Issue | ISSN |
103 | 2 | 0020-0190 |
Citations | PageRank | References |
0 | 0.34 | 4 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Brendan Lucier | 1 | 638 | 52.17 |
| Tao Jiang | 2 | 1809 | 155.32 |
| Ming Li | 3 | 5595 | 829.00 |