### Stack depth of the modified Quicksort algorithm recursion array sorting quicksort stack    Posted: 7 years ago Updated: 6 years ago Edit answers (1) views (3753)

If we execute the recursive procedures by using a stack that contains parameter values for each recursive call, what would be the stack depth of the modified Quicksort algorithm ? Assume that the array parameters are represented by pointers.

 Posted: 7 years ago 0 0 Edit Since we assume that the array parameters are represented by pointers, the information on each recursive call on the stack requires $$O(1)$$ space. The stack depth is the maximum amount of stack space used at any time during a computation. It will be $$\theta(n)$$ on an $$n$$ element input array if there are $$\theta(n)$$ recursive calls to the MODIFIED_Quicksort. When PARTITION (A,p,r) returns q=r-1,i.e, , sequence of recursive calls will be MODIFIED_Quicksort (A,1,n) , MODIFIED_Quicksort (A,1,n-1) , MODIFIED_Quicksort (A,1,n-2) , and so on.