CS502 Fundamentals of Algorithms Assignment 2 Solution Fall 2012

Question 1:

Show that the worst-case running time of MAX-HEAPIFY on a heap of size n is Ω (lg n). 

(Hint: For a heap with n nodes, give node values that cause MAX-HEAPIFY to be called recursively at every node on a path from the root down to a leaf.)


Question 2:

Suppose that the splits at every level of quicksort are in the proportion 1 – α to α, where 0 /b> α which is ≤ 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.)


The minimum depth occurs for the path that always takes the smaller portion Of the split, i.e., the nodes that takes α proportion of work from the parent node.The first node in the path (after the root) gets α proportion of work (the size of Data processed by this node is α n), the second one gets α 2 so on. The recursion Bottoms out when the size of data becomes 1. Assuming the recursion ends at Level m, we have:
α mn = 1
m = lg(1=n)=lg(α)
Similar argument can be used for showing that the maximum depth is-lgn=lg(1-α).