GATE CSE 1990 | Question: 3-v

Question

The complexity of comparison based sorting algorithms is:

• A. $\Theta (n \log n)$
• B. $\Theta (n)$
• C. $\Theta \left(n^2\right)$
• D. $\Theta (n\sqrt n)$

Comments

I think option C should also be included as the bubble sort has average-case complexity as n^2.

---

heap sort is also come under comparison based algorithm so nlogn

Answer 1

First of all which sorting algorithm is being asked? It is not just the normal ones we see in algorithm text books but can be any sorting algorithm which uses comparisons. So, in crux we cannot rely on any specific algorithms for this question.

Now, coming to the options, we can see that $\Theta$ notation is used. We use $\Theta$ notation for a problem when

1. we have a lower bound for the solution -- that is any algorithm which solves the problem must have minimum this much complexity (time complexity being implied)
2. there exist an algorithm which solves the problem with above minimum time complexity (worst case input being implied)

For comparison based sorting we already have known algorithms like heap sort and merge sort, which solves the problem in $O(n \log n)$ $($See $O)$ and now if we show that this is the best possible by any algorithm our answer becomes $\Theta (n \log n).$

And it is indeed proved that for comparison based sorting minimum $\Omega(n \log n)$ comparisons are required and considering time taken being proportional to the number of comparisons, the time complexity is also $\Omega(n \log n).$ Proof of this is given here but in essence it says

• The output of sorting $n$ elements can be any of the $n!$ permutations.
• Each comparison reduces the possibility by $2$
• So, to finish all $n!$ permutations we need minimum $\lg n!$ comparisons which is $\Omega (n \lg n)$

Now, if someone asks what is the minimum number of comparisons to sort $5$ elements answer is definitely $\geq$ $\lg 5! \geq \lg 120 \geq 7. $ We can only use $\geq$ here and not $=$ unless we prove that we can do it in $7$ comparisons. But interestingly, this $\geq$ becomes $=$ till $n = 11$ as given in below Wikipedia link.

Ref: https://en.wikipedia.org/wiki/Comparison_sort

Answer A. $\Theta (n \log n)$

Comments

nice explaination sir

---

@Arjun Shouldn't it be omega notation instead of theta? Or is it that we can always use theta notation if the 2 conditions given in your answer satisfy? 

 

---

Beautiful explanation !!

Answer 2

Only A & C are possible in Comparision based sorting.   

Algorithm	Time Complexity
	Average	Worst
Quicksort	O(n log(n))	O(n^2)
Mergesort	O(n log(n))	O(n log(n))
Heapsort	O(n log(n))	O(n log(n))
Bubble Sort	O(n^2)	O(n^2)
Insertion Sort	O(n^2)	O(n^2)
Select Sort	O(n^2)	O(n^2)

$$\textbf{Time  Complexity}$$

$$\begin{array}{|l|l|}\hline \textbf{Algorithm} & \textbf{Average} & \textbf{Worst} \\\hline \text{Quicksort} & O(n\ log\ n) & O(n^{2})   \\\hline  \text{Mergesort} & O(n\ log\ n) & O(n\ log\ n)   \\\hline \text{Heapsort} & O(n\ log\ n) & O(n\ log\ n)   \\\hline \text{Bubble sort} & O(n^{2}) & O(n^{2})   \\\hline \text{Insertion sort} & O(n^{2}) & O(n^{2})   \\\hline  \text{Selection sort} & O(n^{2}) & O(n^{2})   \\\hline \end{array}$$

Comments

When question says "The complexity of comparision based sorting algorithms" we should consider all comparison based algorithms together and not separately. So, answer must be A and C is false.

---

@Arjun sir Isn't the question is asking what are the complexities possible in comparision based sorting

Just option A is Θ(nlogn) whereas for selection sort and bubble sort Θ(n²)

So we should consider both 

---

               Arjun sir  please explain

When question says "The complexity of comparision based sorting algorithms" we should consider all comparison based algorithms together and not separately. So, answer must be A and C is false.?? 

---

Why both n$\Theta \left ( n^2 \right ) and \Theta \left ( logn \right )$ are not right answer coz bubble sort also do ccomparison