Suppose that the splits at every level of quicksort 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

Question

Douglas Mccormick

Computers & Technology

9 November, 22:24

Suppose that the splits at every level of quicksort 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

+4

Answers (1)

Know the Answer?

Libby Lamb · Answer 1

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 the work (the size of data

processed by this node is αn), the second one get (2)

so on. The recursion bottoms

out when the size of data becomes 1. Assume the recursion ends at level h, we have

(ℎ) = 1

h = log 1 / = lg (1/) / lg = - lg / lg

Maximum depth m is similar with minimum depth

(1 - ) () = 1

m = log1 - 1 / = lg (1/) / lg (1 - ) = - lg / lg (1 - )