The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+5 votes
226 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 (367 points) | 226 views

2 Answers

+1 vote
  • C and D cannot be the answer , since they require stack for recursive calls.
  • A and B , both are inplace sort and have Space complexity of O(1).

The answer should be A .. insertion Sort because in best case the number of comparisons become O(n).

 

answered by Active (2k points)
0 votes
C.Quick Sort is Inplace algorithm with max O(n^2) only for ascending or descending order elements.
answered by Active (1.1k 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.


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

28,947 questions
36,793 answers
91,077 comments
34,690 users