SPACE COMPLEXITY

Question

Comments

which comment?

---

why insertion sort = O(1) + O(n)  = O(n) ?? It is inplace. If O(n) means original array space then it should be O(n) + O(logn) in quicksort?

---

@lokesh

quicksort how it is log(n) recursive calls.

Answer 1

 Insertion sort  $O(n)$
 Quick sort  $O(n) +O( \log n ) $
 merge sort
 Top Down $O(n) +O( \log n ) $
Bottom Up $O(n)$
 selection sort = $ O(n)$

None of the option matches

Answer 2

• 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).

Answer 3

C.Quick Sort is Inplace algorithm with max O(n^2) only for ascending or descending order elements.

Comments

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.