CS136 Study Guide - Binary Tree, Quicksort, Insertion Sort
Document Summary
Assume h[1n] is a max-heap with distinct keys. A2q2. (a) in the worst case, an about right" pivot is chosen so that l = 3. So each recursive call decreases the size of the problem by at least a factor of 4/3. Thus the depth of the recursive calls can be at most log4/3 n. 4 m and r = 1 (b) a perfect binary tree of height h has 2h leaves, so when h = log4/3 n there number of leaves is. 2log4/3 n = 2log n/ log(4/3) = (2log n)1/ log(4/3) = n1/ log(4/3). (c) of the n! total permutations, (n 1)! have the minimum element rst, so there is a (n 1)! of pivoting on the minimum. Similarly, there is a 1 there are n/2 good pivots, there is a n/2 n probability n probability of pivoting on the kth smallest element. Since n = 1/2 probability of choosing a good pivot. n!
