Average Case Analysis of QuickSort and Insertion Tree Height Using Incompressibility - Jiang, Tao; Li, Ming; Lucier, Brendan (Information Processing Letters 2007, 2005)
In this paper we study the Kolmogorov Complexity of a Binary Insertion Tree. We obtain a simple incompressibility argument that yields an asymptotic analysis of average tree height. This argument further implies that the QuickSort algorithm sorts a permutation of n elements in Ɵ (n log n) comparisons on average.