Question

Explain why recursive implementation of QuickSort will require O(log n) of additional space.

Answer 1

Solution:

Explanation:

Quick sort:

=>Quick sort is a sorting algorithm and is used to sort the elements in the array.

=>Quick sort algorithm is based on the devide and conquer algorithm which uses partiotioning method means deviding the array based on the pivot element.

=>Quick sort can be implemented using recursion as well as without recursion.

=>When quick sort is implemented without recursion it required constant space that is O(1) because no recursive step is there so no need to have stack data structure.

=>When quick sort is implemented with recursion then iterative partitioned are required and recursive calls are made.Each recursive call require constant space that is O(1) and in the best case there can be log(n) recursive calls.

=>Hence total extra space in stack = logn*O(1)

=>Total additional space = O(log(n))

I have explained each and every part with the help of statements attached to it.