edited by
439 views
0 votes
0 votes

Assume that the splits at every level of Quick-Sort are in proportion $1-p$ to $p$, where $p (0 < p \leq 0.5 )$ is a constant.  The number of elements in an array is $n$. The maximum depth is approximately:

  1. $0.5 \ p \ \text{lg } n$
  2. $0.5 \ (1 - p) \ \text{lg } n$
  3. $p (\text{lg }n) / (\text{lg }p)$
  4. $- (\text{lg }n) / \text{lg }(1 - p)$
edited by

1 Answer

Best answer
10 votes
10 votes
The minimum depth follows a path that always takes the smaller part of partition  i.e, that multiplies the number of elements by p .

One iteration reduces the number of elements from n to pn , and i iterations reduces the number of elements to pin .

 At a leaf, there is just one remaining element, and so at a minimum depth leaf of depth m, we have pmn = 1.

Thus, pm = 1/n.

Taking logs,

we get m log p = - log n

=>m = - log n / log p .

Similarly, maximum depth corresponds to always taking the larger part of the partition, i.e., keeping a fraction 1 - p of the elements each time.

The maximum depth M is reached when there is one element left,

Thus, M = - lg(n) / lg(1 - p ).
selected by
Answer:

Related questions

0 votes
0 votes
1 answer
1
Bikram asked May 26, 2017
463 views
The cost of optimal binary search tree for the identifier set $(a1, a2, a3) =$ (do, if, while) with $p(1) = 0.3, \ p(2) = 0.2, $ $p(3) = 0.15, q (0) = 0.05, q(1) = 0.15...
2 votes
2 votes
2 answers
3
Bikram asked May 26, 2017
341 views
Assume Dijkstra's Algorithm is used to find the shortest paths from node G in the above graph. The total number of edges which are not included in any of the shortest pat...
1 votes
1 votes
2 answers
4
Bikram asked May 26, 2017
454 views
The total number of LCS (Longest Common Subsequences) of $P = abcd123$ and $Q= badc321$ that can be formed are ______.