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

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?

---

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

We can do as you said, But it will be considered as a variation of insertion sort.

For example, In Array $A[1, \dots , n],$ for any element $A[i] = x,$ we can also use Binary Search to find the correct place for $x$ and then insert $x$ in that position by shifting to make room for it.  See the following GATE 2003 Question.

Usual Insertion sort idea is:
For each element in the collection to be sorted(Remaining unsorted array to the right), insert it into its proper place in another sorted collection(already sorted part to the left).
In the insertion sort algorithm, elements need to be shifted over to make room for the new elements. Insertion sort works the way many people sort a hand of playing cards. We start with an empty left hand and the cards face down on the table. We then remove one card at a time from the table and insert it into the correct position in the left hand. To find the correct position for a card, we compare it with each of the cards already in the hand, from right to left.

Another Variation of Insertion Sort:

https://inst.eecs.berkeley.edu/~cs61bl/r//cur/sorting/insertion-sort.html?topic=lab25.topic&step=2&course=#:~:text=Insertion%20sort%20variation%3A%20Tree%20sort 

---

@fred20978, The variation of insertion sort that you have suggested takes $\Theta(n^2)$ time in each case, So, it is Not better than the usual insertion sort which takes $\Theta(n)$ time in best case. 

---

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

---

I think modified bubble sort not mentioned so we have to take best case of bubble sort as θ(n^2) only.Isn't it?

---

@Arjun Sir, Why is this Ques tagged Ambiguous?

---

It is given input is already sorted , and we can actually optimize merge sort for this , making option c true .

But i think standard books dont consider this optimization as standard.

Optimize: compare last element of first sorted subarray1 with first element of suarray 2.

If less than we skip all merge procedure and for sorted input this really holds

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

@Afzal629 yes that's true but in the question they have taken it to be either 1st or last element as the pivot, otherwise if array is sorted and pivot is middle then it's nlogn time.

As almost every partition will be divided in two halves until we are remain with 1 element partition.

Therefore for logn levels and n elements selected as pivot we would have nlogn time.

---

 

It should be Like "Merge never take less than nlogn"

 

 

---

Siddiqui_Danish  

It's in theta notation meaning it'll never take more or less that nlogn...

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.