1 votes 1 votes Algorithms space-complexity sorting ace-test-series + – santhoshdevulapally asked Dec 15, 2016 retagged Jul 8, 2022 by Lakshman Bhaiya santhoshdevulapally 985 views answer comment Share Follow See all 8 Comments See all 8 8 Comments reply Lokesh . commented Dec 15, 2016 reply Follow Share Total = space + runtime complexity A) insertion sort = O(1) + O(n) = O(n) B) Quick sort = O(log n) + O(log n) = O(log n) C) merge sort = O(n) + O(log n) = O(n) D) selection sort = O(1) + O(n) = O(n) so I think quick sort is rt?? 0 votes 0 votes santhoshdevulapally commented Dec 15, 2016 reply Follow Share in selection sort ,less no of recursive calls compared to quick sort. only one element is swapped at a time,but in quick sort (n-1) swaps in worst case.am i right? 0 votes 0 votes thor commented Dec 15, 2016 reply Follow Share @lokesh in insertion sort O(n) = data space rt?? then in quicksort also we require data space of O(n) + log(n) for stack 1 votes 1 votes Lokesh . commented Dec 15, 2016 reply Follow Share space complexity of in-place algorithms are O(1) and insertion, selection and quick sort are in-place algorithm but in quick sort at each recursion we need one pivot so it need log(n) for that 0 votes 0 votes thor commented Dec 15, 2016 reply Follow Share Why have you written $O(n)$ space complexity in your earlier comment? 0 votes 0 votes 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.