The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+29 votes
3.8k views

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$
asked in Algorithms by Veteran (69k points) | 3.8k views

Video might be useful

3 Answers

+32 votes
Best answer
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.
answered by Veteran (346k points)
selected by
Yes.. I. Got you sir.
But. If a question comes in gate that what ate the comparisons in best and worst case in merge sort then answer will be nlogn.. Right??

And. In these types of. Questions, we should always consider. That. Sorting algorithm. Which takes. The minimum of all the other in the criteria??
Yes. that is the general rule. Always consider the best algorithm or method or implementation for any subject question but consider the worst input possible unless specified otherwise.

Tightest lower bound of sorting (say S(n)) is nlog⁡n means there is no function f which has an order of growth larger than nlog⁡n and f(n)=Ω(S(n)) holds.

Sir, if we are saying that the tightest lower bound  is nlog⁡n then it means there is no function f which has an order of growth smaller than nlog⁡n and f(n)=Ω(S(n)) should hold.

Sir please correct me if I am having wrong concept.

No, it should be "larger". Otherwise take $f(n) = n$ is smaller than $f(n) = n\log n$ and $f(n) = \Omega(S(n))$ does hold.

PS: That line is explaining "tightest" and not "lower bound".
Thank You Sir.

I am so much confused. Feeling as if this concept is out of my reach.

If f(n) = n and S(n)=nlogn then f(n) = O(S(n)) should hold.Why you have written it the other way?

Also, I am not getting the difference between "tightest" and "lower bound".

Please suggest some source if possible.

Even God's sorting algorithm takes Ω(n logn) comparisons in the worst case.

read question properly...actually asked that worst time complexity of best algo among all comparision base algo's

@Arjun Sir,The first statement of the answer says:-

For comparison-based sorting the asymptotically tight bound for worst case is given by Θ(nlogn)

This is for optimal comparison based sorts(heap,merge),right?

Because worst case of all comparison based is not nlogn ? Reading this line it seems to be true for all ,but cases like insertion sort,bubble sort does not fit this.Please clear this point

Rajendra Dangwal even I have this doubt , if now u understood it then pls help me.

For the worst case, tighest lower bound in all comparison based sorting algo means - In the worst case which sorting algorithm take the least time to sort. So,  O(nlog) because in the worst case we can't sort in less time than this if it would have been upper bound then it can be infinite.

For best case, tighest lower bound in all comparison based sorting algo means - In the best case, which sorting algorithm take the least time to sort. So O(n) because we can't sort in less time than this if it would have been upper bound then I think it would have been infinite.

please correct me if I am wrong?
+2 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.

answered by Veteran (14.7k points)
edited by
+2 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

answered by (143 points)


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

33,687 questions
40,230 answers
114,269 comments
38,800 users