in Algorithms retagged by
370 views
0 votes
0 votes

 

 

Ans given is option-B

in Algorithms retagged by
370 views

1 Answer

0 votes
0 votes
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.

7 Comments

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

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.

0
0

can refer this video for a visual understanding.
https://www.youtube.com/watch?time_continue=57&v=wObxd4Kx8sE

0
0
@vikas

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