Suppose that the splits at every level of quick sort are in the proportion 1 - α to α, where 0 < α ≤ 1/2 is a constant. Show that the minimum depth of a leaf in the recursion tree is approximately - lg n/ lg α and the maximum depth is approximately -lg n/ lg(1 - α). (Don't worry about integer round-off.)
Answer to relevant QuestionsWhy do we analyze the average-case performance of a randomized algorithm and not its worst-case performance?Which of the following sorting algorithms are stable: insertion sort, merge sort, heap sort, and quick sort? Give a simple scheme that makes any sorting algorithm stable. How much additional time and space does your scheme ...Suppose that you have a "black-box" worst-case linear-time median subroutine. Give a simple, linear-time algorithm that solves the selection problem for an arbitrary order statistic.What is the difference between the binary-search-tree property and the min-heap property (see page 129)? Can the min-heap property be used to print out the keys of an n-node tree in sorted order in O(n) time? Explain how or ...Professor Teach is concerned that RB-INSERT-FIXUP might set color [nil [T]] to RED, in which case the test in line 1 would not cause the loop to terminate when z is the root. Show that the professor's concern is unfounded by ...
Post your question