GATE CSE
First time here? Checkout the FAQ!
x
+3 votes
96 views
Which algorithm has smallest memory requirement in terms of data space and runtime stack(for recursive calls)? (Low Space Complexity)

A. Insertion sort

B. Selection sort

C. Quick Sort

D. Merge Sort
asked in Algorithms by (143 points)   | 96 views

1 Answer

0 votes
C.Quick Sort is Inplace algorithm with max O(n^2) only for ascending or descending order elements.
answered by (457 points)  
Please specify space complexity for all.

What about sorting technique that by default have no runtime stack?

So if we have no runtime stack for sorting, that sorting should become more selective over sorting with runtime stack.

So, quick sort is having runtime stack, so it should not answer.

Correct me if I am wrong.
why not A and B?  I think Quicksort space complexity will be more than Insertion or selection, we even dont need any recursion for A and B and for quicksort we need atleast one recursion call.
Top Users Jan 2017
  1. Debashish Deka

    7172 Points

  2. Habibkhan

    4696 Points

  3. Vijay Thakur

    4308 Points

  4. sudsho

    4090 Points

  5. saurabh rai

    4024 Points

  6. Arjun

    3292 Points

  7. santhoshdevulapally

    3066 Points

  8. GateSet

    3016 Points

  9. Bikram

    3014 Points

  10. Sushant Gokhale

    2892 Points

Monthly Topper: Rs. 500 gift card

18,838 questions
23,808 answers
51,589 comments
20,148 users