QuickSort's estimation of recursion depth

Question

Being the recursion depth the maximum number of successive recursive calls before QuickSort hits it´s base case, and noting that it (recursion depth) is a random variable, since it depends on the chosen pivot.

What I want is to estimate the minimum-possible and maximum-possible recursion depth of QuickSort.

The following procedure describes the way thats QuickSort is normally implemented:

QUICKSORT(A,p,r)
    if p<r
        q ← PARTITION(A,p,r)
        QUICKSORT(A,p,q−1)
        QUICKSORT(A,q+1,r)
    return A

PARTITION(A,p,r)
    x←A[r]
    i←p−1
    for j ←p to r−1
        if A[j] ≤ x
            i ← i +1
            exchange A[i] ↔ A[j]
    exchange A[i +1] ↔ A[r]
    return i +1

The second recursive call in QuickSort is not really necessary; it can be avoided by using an iterative control structure. This technique is also called tail recursion, and it can be implemented like:

QUICKSORT_tail(A,p,r)
    while p<r
        q ← PARTITION(A,p,r)
        QUICKSORT(A,p,q−1)
        p ← q+1
    return A

In this version, the information for the most recent call is at the top of the stack, and the information for the initial call is at the bottom. When a procedure is invoked, its information is pushed onto the stack; when it terminates, its information is popped. Since I assume that array parameters are represented by pointers, the information for each procedure call on the stack requires O(1) stack space. I also believe that the maximum-possible stack space with this version should be θ(n).

So, after all this said, how can I estimate the minimum-possible and maximum-possible recursion depth of each QuickSort version? Am I right in the above inference?

Thanks in advance.

Answer 1

Worst-case

The worst-case behavior for quicksort occurs when the partitioning routine produces one subproblem with n -1 elements and one with 0 elements.The partitioning costs θ(n) time. If the partitioning is maximally unbalanced at every recursive level of the algorithm, then the depth of the tree is n and the worst case is θ(n) the worst-case behavior for quicksort θ(n^2), as you see the number of the last level of the corresponding recursion tree in the worst case is θ(n).

Best-case

In the most even possible split, PARTITION produces two subproblems, each of size no more than n=2, since one is of size floor(n/2) and one of size floor(n/2) -1. In this case, quicksort runs much faster.The recursion tree in this case is what is known as complete binary tree It can have between 1 and 2h nodes, as far left as possible, at the last level h, then h = log n, then the best-case behavior for quicksort θ(nlog n), and as you see the number of the last level of the corresponding recursion tree in the best case is θ(log n).

Conclusion

Minimum: θ(log(n))

Maximum: θ(n)