33,225 views
77 votes
77 votes

The tightest lower bound on the number of comparisons, in the worst case, for comparison-based sorting is of the order of

  1. $n$
  2. $n^2$
  3. $n \log n$
  4. $n \log^2n$

5 Answers

Best answer
85 votes
85 votes
For comparison-based sorting the asymptotically tight bound for worst case is given by $\Theta (n \log n)$, which means it is the tightest upper bound (big O) as well as the tightest lower bound (big omega). So, answer is $n \log n$.

Tightest lower bound of sorting (say S$(n)$) is $n \log n$ means there is no function $f$ which has an order of growth larger than $n \log n$ and $f(n) = \Omega (S(n))$ holds.

A usual mistake is to think worst case changes with lower and upper bounds, but that is not the case. Worst case is defined for the algorithm and it is always the input which causes the algorithm the maximum complexity.

Correct Answer: $C$
edited by
9 votes
9 votes

There is no comparison based sorting algorithm which can perform sorting in less then nlogn in worst case. For proof of this statement please refer https://www.youtube.com/watch?v=voftwFuqH4I or check CLRS. So this is the tightest lower bound for comparison based sorting algorithm in worst case.

edited by
3 votes
3 votes

An n log n lower bound for sorting


Sorting algorithms can be depicted as trees. The depth of the tree - the number of comparisons on the longest path from root to leaf, is exactly the worst-case time complexity of the algorithm. This way of looking at sorting algorithms is useful because it allows one to argue that mergesort is optimal, in the sense that Ω(n log n) comparisons are necessary for sorting n elements.

Here is the argument: Consider any such tree that sorts an array of n elements. Each of its leaves is labeled by a permutation of {1, 2, ....., n}. In fact, every permutation must appear as the label of a leaf. The reason is simple: if a particular permutation is missing, what happens if we feed the algorithm an input ordered according to this same permutation? And since there are n! permutations of n elements, it follows that the tree has at least n! leaves.

We are almost done: This is a binary tree, and we argued that it has at least n! leaves. Recall now that a binary tree of depth d has at most 2d leaves (proof: an easy induction on d). So, the depth of our tree - and the complexity of our algorithm - must be at least log(n!).

And it is well known that $log(n!) \geq c.nlogn$ for some c > 0. There are many ways to see
this. The easiest is to notice that $n! \geq (n/2)^{n/2}$ because n! = 1*2*3.......*n contains at least n/2 factors larger than n/2; and to then take logs of both sides. Another is to recall Stirling's formula:
$n! \approx \sqrt{\pi (2n + 1/3)}.n^{n}.e^{-n}$

Either way, we have established that any comparison tree that sorts n elements must make, in the worst case,  Ω(n log n) comparisons, and hence mergesort is optimal!

Source: Algorthms by Dasgupta, Papadimitriou, Vazirani PN 59

0 votes
0 votes
This is asking no. of comparison needed in worst case to sort the elements. Why we are taking references of merge sort and any other. In merge sort the no. of comparisons to sort the elements is O(n). But if we go by traditional approach like if we have N elements and we need to sort it. Then it has n! to permute the elements out of which we have one correct sequence of elements hich has correct sorted order.

If the algorithm always completes after at most f(N) steps, it cannot distinguish more than 2^f(N) cases because the keys are distinct and each comparison has only two possible outcomes. Therefore,

2^f(N) >= N! or equivalently f(N) >= log(N!).
Since log(N!) is Omega(NlogN), the answer is NlogN.
Answer:

Related questions

42 votes
42 votes
4 answers
1
Kathleen asked Sep 18, 2014
11,948 views
Two matrices $M_1$ and $M_2$ are to be stored in arrays $A$ and $B$ respectively. Each array can be stored either in row-major or column-major order in contiguous memory ...
15 votes
15 votes
7 answers
2
Kathleen asked Sep 18, 2014
11,672 views
The problem $\text{3-SAT}$ and $\text{2-SAT}$ are both in $\text{P}$both $\text{NP}$ complete$\text{NP}$-complete and in $\text{P}$ respectivelyundecidable and $\text{NP}...
38 votes
38 votes
4 answers
3
Kathleen asked Sep 18, 2014
8,310 views
The following finite state machine accepts all those binary strings in which the number of $1$’s and $0$’s are respectively: divisible by $3$ and $2$odd and evene...
37 votes
37 votes
7 answers
4
Kathleen asked Sep 18, 2014
12,554 views
The minimum number of colours required to colour the following graph, such that no two adjacent vertices are assigned the same color, is$2$$3$$4$$5$