edited by
14,163 views
43 votes
43 votes

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
  1. I and II only
  2. I and III only
  3. II and IV only
  4. I and IV only
edited by

4 Answers

Best answer
48 votes
48 votes
  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$

edited by
3 votes
3 votes

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

edited by
0 votes
0 votes
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
0 votes
0 votes
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.
Answer:

Related questions