1 votes 1 votes Algorithms space-complexity sorting ace-test-series + – santhoshdevulapally asked Dec 15, 2016 • retagged Jul 8, 2022 by Lakshman Bhaiya santhoshdevulapally 1.1k views answer comment Share Follow See all 8 Comments See all 8 8 Comments reply Show 5 previous comments Lokesh . commented Dec 15, 2016 reply Follow Share which comment? 0 votes 0 votes thor commented Dec 15, 2016 reply Follow Share 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? 0 votes 0 votes santhoshdevulapally commented Dec 15, 2016 reply Follow Share @lokesh quicksort how it is log(n) recursive calls. 0 votes 0 votes Please log in or register to add a comment.
1 votes 1 votes 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 pC answered Dec 15, 2016 pC comment Share Follow See all 0 reply Please log in or register to add a comment.
1 votes 1 votes 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). shaurya vardhan answered Nov 4, 2017 shaurya vardhan comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes C.Quick Sort is Inplace algorithm with max O(n^2) only for ascending or descending order elements. aik138463 answered Nov 3, 2016 aik138463 comment Share Follow See all 2 Comments See all 2 2 Comments reply parthbkgadoya commented Dec 4, 2016 reply Follow Share 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. 0 votes 0 votes Surajit commented Jan 3, 2017 reply Follow Share 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. 1 votes 1 votes Please log in or register to add a comment.