Stack depth of the modified Quicksort algorithm
  • recursion
  • array
  • sorting
  • quicksort
  • stack
  •   
  • Posted: 5 years ago
  • Updated: 4 years ago
  • Edit
  • answers (1)
  • views (2617)

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 Answers

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.

You need to Sign In to post your solution.