[36/O39] Consider the following algorithm. QuickSort( Array [1..n] ): If n = 1 then return ; p := [1]; L := (x , x

[36/O39] Consider the following algorithm.

QuickSort( Array π[1..n] ): If n = 1 then return π; p := π[1]; πL :=

(x ∈ π, x < p) in stable order; πR := (x ∈ π, x > p) in stable order;

QuickSort(πL); QuickSort(πR); π := πLpπR.

(a) Use the incompressibility method to show that the average height of a Quicksort tree (its deepest recursion level), or equivalently a binary insertion tree, is O(log n). This also gives an alternative O(n log n)

average-case analysis of Quicksort.

(b) Obtain the 4.31107 logn upper bound using the incompressibility method.

Comments. Hint: Consider a pivot sequence (p1, p2,...,pk), where pi+1 is a pivot for one of the subranges defined by pi for all i. The longest such sequence corresponds to the binary search tree height. This sequence can be encoded efficiently. Suppose π has a pivot chain of length c log n, where c is sufficiently large. Let x be the string of length c log n such that x[i] = 1 iff pi occurs in the middle half of its range. Let z be the string of length c log n such that z[i] = 1 iff pi+1 is the pivot for the smaller range defined by pi. Then the number of ones in x is at most c log n, where c = 1/ log 4 3 , and the number of ones in z is at most log n, since otherwise the size of the ranges for the pi will reach 1. Now note that if we are given x and z, we can save one bit for every entry pi in π, since pi begins in 01 or 10 iff x[i] = 1, and z tells us which of pi’s subpivots is pi+1. Thus, given x and z, we save c log n bits from the encoding of π. Now π can be computably encoded by log(A!) = log A B +log(B!)+log((A−B)!) while compressing the pivots along the pivot sequence. Source: [B. Lucier, T.
Jiang, and M. Li, Inform. Process. Lett., 103:2(2007), 45–51]. A tight bound for this problem by probabilistic analysis is given in [L. Devroye, J. Assoc. Comp. Mach. 33:3(1986), 480–498].