The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+29 votes

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

- $n$
- $n^2$
- $n \log n$
- $n \log^2n$

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

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.

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??

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)) isnlognmeans there is no functionfwhich has an order of growth larger thannlognandf(n)=Ω(S(n))holds.

Sir, if we are saying that the tightest lower bound is **nlogn** then it means there is no function** f** which has an order of growth smaller than **nlogn** 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".

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.

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.

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?

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

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

+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

- All categories
- General Aptitude 1.2k
- Engineering Mathematics 4.7k
- Digital Logic 1.9k
- Programming & DS 3.5k
- Algorithms 3k
- Theory of Computation 3.7k
- Compiler Design 1.5k
- Databases 2.8k
- CO & Architecture 2.5k
- Computer Networks 2.9k
- Non GATE 837
- Others 1.2k
- Admissions 278
- Exam Queries 396
- Tier 1 Placement Questions 17
- Job Queries 50
- Projects 7

33,687 questions

40,230 answers

114,269 comments

38,800 users