Ask Question
25 June, 05:00

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)
  1. 25 June, 06:03
    0
    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 - )
Know the Answer?
Not Sure About the Answer?
Find an answer to your question ✅ “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 ...” in 📘 Computers and Technology if you're in doubt about the correctness of the answers or there's no answer, then try to use the smart search and find answers to the similar questions.
Search for Other Answers