370 views

Ans given is option-B

Yes that's right because

A) insertion sort would need O(n) space for data and O(n) stack space.

C) merge sort would take O(n) data space and O(n logn) stack space. Hint: it is an outplace algorithm

D) same as A

B) takes O(n) data space and O(logn) stack space in all cases except the worst.

Can you please explain how to calculate stack spce?
How insertion sort take stack space n ?

Let's consider insertion sort.

void insertionSortRecursive(int arr[], int n)
{
// Base case
if (n <= 1)
return;

// Sort first n-1 elements
insertionSortRecursive( arr, n-1 );

// Insert last element at its correct position
// in sorted array.
int last = arr[n-1];
int j = n-2;

/* Move elements of arr[0..i-1], that are
greater than key, to one position ahead
of their current position */
while (j >= 0 && arr[j] > last)
{
arr[j+1] = arr[j];
j--;
}
arr[j+1] = last;
} 

Stack space is just the number of stack records required which is the number of function calls done, whose worst case would be when we have greatest extent of recursive calls without backtracking.

If you see the recursive call in this. It says insertionSortRecursive( arr, n-1 ) which means it reduces the size of the array by 1 in each recursive call. Hence the recurrence relation for stack space becomes
T(n) = T(n-1) +1
which results in O(n)

Here quick sort being an inplace algorithm taking O(logn) stack space would require the least amount of space among all of them.

can refer this video for a visual understanding.

@vikas

Space complexity of insertion sort is O(1) noe?
Yes, but for iterative algorithm. Here the question is of the recursive algorithm which uses a stack.
Thanks

1 vote