GATE CSE 2016 Set 2 | Question: 13

Question

Assume that the algorithms considered here sort the input sequences in ascending order. If the input is already in the ascending order, which of the following are TRUE?

1. Quicksort runs in $\Theta (n^2)$ time
2. Bubblesort runs in $\Theta (n^2)$ time
3. Mergesort runs in $\Theta (n)$ time
4. Insertion sort runs in $\Theta (n)$ time

• A. I and II only
• B. I and III only
• C. II and IV only
• D. I and IV only

Comments

@Deepak Poonia Why is it called a variation?

For this case the sort i mentioned takes O(n^2). But it have its own best case scenario which would be descending order and it take O(n) times for that.

So what makes us say that which insertion sort is the original one? everything uses the same idea. Is it based on whats mentioned in standard text? or is it because the usual insertion sort idea is stable?

or maybe gate would be assuming the usual one as default case?

---

@fred20978

The idea that you have mentioned takes $\Theta(n^2)$ time in all cases, even if the array is reverse sorted.

Also, you can make more variants of usual insertion sort, for example, by using linked list instead of array, Or the two variants I mentioned in my previous comment.

---

O(n^2). isn't it Because of the number of swaps? Okay i think i got it.

Answer 1

1. Quicksort takes $\Theta(n^2)$ in case of already sorted input. This is true
2. This is false. If no swap happens then bubble sort can stop in single loop. $\Theta(n)$ is best case. This is false!
3. Mergesort never takes more than $\Theta(n \log n)$ This is false
4. This is true. Insertion sort will finish in $\Theta(n)$ time in case of sorted input.

Answer D. I and IV.

Proof Bubble sort has best case $O(n):$

 Ref: https://en.wikipedia.org/wiki/Bubble_sort, Aduni lecture

Now quicksort taking $\mathbf{O(n \log n)}$ can happen in some cases but not all cases, so that is why I) should be considered true. Whereas Bubble sort time complexity in best case is always $\mathbf{O(n)}$. So, D is any time stronger answer than C .

Correct Answer: $D$

Comments

https://www.geeksforgeeks.org/comparison-among-bubble-sort-selection-sort-and-insertion-sort/

 

see this comparison between selection sort ,bubble sort and insertion sort.

here clear mention modified bubble sort has best case complexity O(N).

---

In insertion sort why we are comparing the elements considered from the right side already sorted part of the array? ie; consider elements 1,2,3,4,5 now 1,2,3 are already sorted and we take element 4 why we are considering to check 4 with 3 first cant we check 4 with 1 then 2 then 3 and get the correct position to insert?

---

@fred20978 Answered your doubt here:

https://gateoverflow.in/39561/gate-cse-2016-set-2-question-13?show=393130#c393130 

Answer 2

"Q=Q can be used instead of Theta."

"Case I : Quick Sort takes Q(N^2) in case of already sorted input. This is true."

"But does Quick Sort always take first element as pivot?"

It is not mentioned anywhere in the question that Quick sort takes first / last element as PIVOT.

Q(N^2) is only possible if Pivot is First or last element , at the same time array is sorted, with recurrence relation of time complexity T(n) as follows-

T(n)= O(1) [Pivot selection time] + O(N)[Division/Partition Time] + (T(n-1)+T(1)) [Conquer/Recursive call Time] + O(1) [Combine time]  

        = Q (n^2)

But if I take a randomized Pivot Element for the quick sort which is anyhow not the first or last element of the sorted array , then the recurrence equation of the “Conquer or Recursive Call” part may change to T(n)=T(n/2)+T(n/8) or may be in T(n)=T(n/5)+T(4n/5) which leads in to time complexity Q (N.logN) of that part.

So time Complexity depends on selection of the Pivot element even if the array is sorted.

"Case II : This is false. If no swap happens then bubble sort can stop in single loop. Q(N) is best case. This is false ! "

"But bubble sort needs modification to ensure that."

"Modified bubble sort would take theta(n) time in best case."

If we modify our coding so that if the last two passes have the same result with no change, then only it’s Q(n), otherwise Q(N^2). Why?

Because Bubble sort time complexity depends on two things No of comparisons made and also No of swaps occur. If the array is sorted but not a modified bubble sort is done then even if the no of swaps is Q(1) but still the number of comparisons in 1st pass is (n-1), in second pass is (n-2) and in 3rd pass is (n-3) and so on.... till last pass which results in to Q(N^2) time complexity of bubble sort, if it is not modified.

If it is modified Time complexity is of linear time Q(n) !!

Last two cases are pretty straight Forward i think no confusion everyone can easily judge it ..... 

"Case III : Merge Sort never takes more than Q(N.logN). This is false."

and

"Case IV : Insertion Sort will finish in Q(N) time in case of sorted input. This is true."

So the question leads to an Ambiguous Tagged one.

Answer 3

Insertion sort runs in O(n) time if the input is already sorted.

Whatever the input may be bubble sort will run O(n^2) time

Hence Option C

Comments

In best case(if input is already sorted), bubble sort takes O(n) time. While in quicksort, worst case is when the input is already sorted or all the elements are equal.

Hence option D is correct !

---

It depends on which version of bubble sort is used , quicksort with random pivot is O(nlogn)

---

@arjun sir why this question gives many aspects  sir plz verify me in case of  quicksort, worst case is when the input is already sorted or all the elements are equal then it takes  O(n^2) and its possible  when pivot element is first or last but if i take random element as pivot then for that it can be take O(nlogn) even input are sorted or all element are equal  but for that they should mention randomized quick sort but they did not  so am going  with general case  in which  quick sort worst case time complexity is O(n^2) .  so for that reason i hit the option D   am i rt  sir ??

2nd thing is  which i m worried so much what is the versions of bubble sort  . i m only know that the best  and  worst case T.C for bubble sort  are  O(n) (when element are sorted )   and O(n^2)  and why u said opion c is also correct in previous comment if u said that it means bubble sort take O(n^2)  in best case bcz question said elemnt are sorted plz verify it 

Answer 4

If input sequence is already sorted then the time complexity of Quick sort will take O(n2) and
 Bubble sort will take O(n) and
Merge sort will takes O(nlogn) and
insertion sort will takes O(n).

→ The recurrence relation for Quicksort, if elements are already sorted,
T(n) = T(n-1)+O(n) with the help of substitution method it will take O(n2).
→ The recurrence relation for Merge sort, is elements are already sorted,
T(n) = 2T(n/2) + O(n) with the help of substitution method it will take O(nlogn).
We can also use master's theorem [a=2, b=2, k=1, p=0] for above recurrence.