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

https://www.cs.auckland.ac.nz/compsci220s1c/lectures/2016S1C/CS220-Lecture08.pdf

Check out slide no 11 and 12.

---

Thanks @palashbehra5 bro

---

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

Thanks a lot bro. But it will be better if you can explain option A in more depth.

---

Let 9n/10 be sorted and n/10 be not sorted part.

For insertion sort:

1^st 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.

---

@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))