0 votes 0 votes Can anyone explain each option, for every option if it is true then why? If false then why? (Please don’t comment like answer is A,B etc) Please help Algorithms algorithms sorting time-complexity multiple-selects test-series + – raja11sep asked Jan 15, 2022 retagged Jul 17, 2022 by makhdoom ghaya raja11sep 831 views answer comment Share Follow See all 5 Comments See all 5 5 Comments reply Show 2 previous comments Kabir5454 commented Jan 17, 2022 reply Follow Share 90% elements are already sorted mean 10% element are not sorted. say no of element is n. no of element not sorted is 0.1n . now the worst case can be imagined as all 0.9n elements are in already sorted order and last 0.1n element are reverse order. to sort the last 0.1n element in worst case it will take O(0.1n * 0.1 n) =O(0.01n^2) =O(n^2) 0 votes 0 votes Nikhil_dhama commented Jan 19, 2022 reply Follow Share Yeah, but remember, if $n \leq 15$, insertion sort is the fastest. 2 votes 2 votes palashbehra5 commented Jan 21, 2022 reply Follow Share Nikhil_dhama Any final days preparation tips, sir? :) 0 votes 0 votes Please log in or register to add a comment.
Best answer 6 votes 6 votes False ( Insertion sort can still take O(n^2) whereas merge sort takes less comparison ) True. Take the case of 2 3 4 5 1 there is at n inversion in this case. But it will lead to O(n) insertion sort comparison and O(n^2) comparison for quick sort (almost sorted case) False. Bubble sort will have O(n^2) comparison whereas in merge sort it is independent of it so again O(n*logn) [Check using above example 1st case 4 comparison then 3 then 2 then 1] False. Again heap always will have O(n logn) and insertion sort will take O(n) This is my solution maybe I am wrong please feel free to correct me. AniketThomas answered Jan 15, 2022 selected Jan 16, 2022 by raja11sep AniketThomas comment Share Follow See all 5 Comments See all 5 5 Comments reply raja11sep commented Jan 16, 2022 reply Follow Share Thanks a lot bro. But it will be better if you can explain option A in more depth. 0 votes 0 votes AniketThomas commented Jan 16, 2022 reply Follow Share Let 9n/10 be sorted and n/10 be not sorted part. For insertion sort: 1st 9n/10 elements will take 1 comparison each(since sorted) = 9n/10 comparison. Starting from 9n/10+1 element it’ll in worst case take 9n/10 comparison(smaller than all) 9n/10+2 element will take 9n/10+1 Total comparison = 9n/10 (first 9n/10) + (9n/10) + (9n/10+1) + (9n/10 + 2) + …… (9n/10 + n/10-1) If you sum it you’ll get O(n^2) which is less than merge sort which has O(nlogn). P.S.: Are my answers correct, just for checking. 3 votes 3 votes raja11sep commented Jan 16, 2022 reply Follow Share @AniketThomas seems correct to me..Thanks again bro. 0 votes 0 votes Shaik Masthan commented Jan 17, 2022 reply Follow Share @AniketThomas, how sum is O(N$^2$) ? 0 votes 0 votes AniketThomas commented Jan 18, 2022 reply Follow Share You can calculate by taking n/10 terms of 9n/10 = n/10*9n/10 = 9n^2/100 (O(n^2)) 2 votes 2 votes Please log in or register to add a comment.