retagged by
6,204 views
17 votes
17 votes

The complexity of comparison based sorting algorithms is:

  1. $\Theta (n \log n)$
  2. $\Theta (n)$
  3. $\Theta \left(n^2\right)$
  4. $\Theta (n\sqrt n)$
retagged by

2 Answers

Best answer
19 votes
19 votes

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

selected by
2 votes
2 votes

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}$$

edited by
Answer:

Related questions

11 votes
11 votes
1 answer
1
makhdoom ghaya asked Nov 19, 2016
5,833 views
Match the pairs in the following questions:$$\begin{array}{|ll|ll|}\hline (a) & \text{Strassen's matrix multiplication algorithm} & (p) & \text{Greedy method} \\\hline (...
29 votes
29 votes
6 answers
3
makhdoom ghaya asked Nov 22, 2016
9,213 views
Indicate which of the following well-formed formulae are valid:$\left(P\Rightarrow Q\right) {\wedge} \left(Q \Rightarrow R\right) \Rightarrow \left(P \Rightarrow R\right)...
20 votes
20 votes
3 answers
4
makhdoom ghaya asked Nov 22, 2016
9,032 views
Let $R_{1}$ and $R_{2}$ be regular sets defined over the alphabet $\Sigma$ Then:$R_{1} \cap R_{2}$ is not regular.$R_{1} \cup R_{2}$ is regular.$\Sigma^{*}-R_{1}$ is regu...