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 ).