Show how to sort n integers in the range 0 to n2 - 1 in O (n) time.
Answer to relevant QuestionsWhat is the worst-case running time for the bucket-sort algorithm? What simple change to the algorithm preserves its linear expected running time and makes its worst-case running time O(n lg n)?Let X [1 .. n] and Y [1 .. n] be two arrays, each containing n numbers already in sorted order. Give an O (lg n)-time algorithm to find the median of all 2n elements in arrays X and Y.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 ...Suppose that the black-height of each of the sub trees α, β, γ, δ, ε in Figures 13.5 and 13.6 is k. Label each node in each figure with its black-height to verify that property 5 is preserved by the ...Describe an efficient algorithm that, given an interval i, returns an interval overlapping i that has the minimum low endpoint, or nil [T] if no such interval exists.
Post your question