Gateoverflow Test series

Question

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

Comments

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)

---

Yeah, but remember, if $n \leq 15$, insertion sort is the fastest.

---

Nikhil_dhama Any final days preparation tips, sir? :)

Answer 1

• A. False ( Insertion sort can still take O(n^2) whereas merge sort takes less comparison )
• B. 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)
• C. 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 1^st case 4 comparison then 3 then 2 then 1]
• D. 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.

Comments

@AniketThomas seems correct to me..Thanks again bro.

---

@AniketThomas, how sum is O(N$^2$) ?

---

You can calculate by taking n/10 terms of 9n/10 = n/10*9n/10 = 9n^2/100 (O(n^2))