GATE CSE
First time here? Checkout the FAQ!
x
+7 votes
321 views
The lower bound on the no. of comparisons required to sort n numbers is __________ ?
asked in Algorithms by Veteran (65.1k points) 35 222 626
edited by | 321 views

2 Answers

+9 votes
Best answer


http://en.wikipedia.org/wiki/Comparison_sort#Number_of_comparisons_required_to_sort_a_list


Hence, upto $N=12$, It is $CEIL(LogN!)$ and after that, it is $O(NLogN)$.

Thank you @Kapil : ) 

answered by Veteran (27k points) 13 48 207
edited by
Can u explain a bit @vijay

How comparison performed?


http://en.wikipedia.org/wiki/Comparison_sort#Number_of_comparisons_required_to_sort_a_list


Hence, upto $N =12$, It is $CEIL(Log N!)$ and after that, it is $O(N Log N)$.

We are asked to find minimum of worst case of all sorting algorithms ? rt?
Yes, @thor .. you are correct... I missed that point.

@Kapil, Please convert your comment as ans. .. good point .. (y).
@vijaycs you can edit your answer making it correct.
lower bound=best case=minimum worst case rt?

then why not O(N)?

@srestha, I too did the same mistake earlier.

But see, Your question asks us to find the lower bound complexity for every input array, not any special case array.

O(n) is for some special case input.( when array is already sorted)

O(nlog n) for a general input. ( irrespective of order of elements).

Lower bound = minimum time even in worst case scenario. but not equal to =best case.( best case is taken for some best possible input order)

 

too good (y)
+9 votes

                                         $$\large\color{green}{\text{Minimum comparison sorting:}}$$

First of all, we will not consider any existing comparison based sorting algorithm, and try to see this problem from a basic point of view of comparison.

Now,
Assume our keys to be distinct. And keys are 

$$\begin{align*} \color{red}{K_1 \;\;K_2 \;\;K_3 \;\;K_4 \;\; ..... K_n } \end{align*}$$

  • Because we are considering distinct keys there are only two possibilities of comparing two keys $K_i$ and $K_j$.
  • Either $K_i > K_j$ or, $K_i < K_j$


This problem of sorting by comparison can also be visualized as follows:

Given a set of $n$ distinct weights and a balance scale, we can ask for the least no of weighings necessary to completely rank the weights in the order of magnitude. The only constraint is we can measure only two weights in a single weighing.

Now we abstract our problem with the following extended binary tree. For this example only 3 keys are taken.

 

  • Each internal node of this tree has two indices $i:j$, denoting comparison is in between $K_i$ and $K_j$.
  • Left subtree of this node represents the subsequent comparisons to be made if $K_i < K_j$.
  • Right subtree of this node represents the subsequent comparisons to be made if $K_i > K_j$.
  • Each leaf node of the tree contains a permutation of all ${K_i}$.
  • Each of those permutations is in a sorted order.


One path trace explanation in the above tree (blue path):


 

  • First compare $K_1$ with $K_2$
  • If $K_1 < K_2$ it goes (via left subtree) on to compare $K_2$ with $K_3$
  • If $K_2 > K_3$ it goes (via right subtree) on to compare $K_1$ with $K_3$
  • If $K_1 > K_3$ we arrive at the leaf node with a sorted sequence of $K_3 <  K_1 < K_2$


Important to note here, is that our priority should be to minimize the no of comparison, and if we see in the tree diagram there is no redundant comparison.


For example, after the violet node, in the left subtree we do not need to compare $K_1$ with $K_3$.

So, now we have an extended binary tree structure in which every leaf node corresponds to a unique permutation of the n keys that we have taken in the beginning.

  • We have $\large\color{maroon}{\text{n!}}$ leaf nodes.

Now we are in a position to analyze the minimum no of comparison to sort $n$ given keys with the help of this comparison tree diagram.

Let $C(n)$ be the minimum no of comparisons that that is sufficient to sort $n$ elements.

Few last observation we need.

  • If we are at a level $k$ in the tree, at that level maximum $2^{k}$ nodes can be present. We understand that all the level will not have always $2^{k}$ nodes (sometimes less). But at max, we can assume that.
  • We start from level $0$ (from the root), then arrive at level $k$, we will be done with k comparisons.
  • This one is important: If all the internal nodes at levels $<$ k, then there can be at most $2^{k}$ leaf nodes. Beyond this k levels, we have only leaf nodes which are nothing but required sorted sequence. Thus we performed k comparisons. So, $C(n) = k$.

$$\begin{align*}
&\Rightarrow  n! \leq 2^{C(n)} \\
&\Rightarrow \left \lceil \log (n!) \right \rceil \leq C(n) \\
&\Rightarrow C(n) \geq  \left \lceil \log (n!) \right \rceil   \\
\\
& \text{Using Stirlings approximation} \\
&\Rightarrow C(n) \geq  \;\; n \log n - \frac{n}{\ln 2} + \frac{1}{2} \log n + O(1) \\
&\Rightarrow C(n) \approx  \;\; n \log n \\
\end{align*}$$



For more on information theoretic lower bound :: knuth volume 3 page 180+.

answered by Veteran (56.9k points) 36 189 500
edited by
bro !!! how long did it took to explain all this ? BTW thanks
2 hours !
@debashish this proves that a comparison based sorting can't take less than nlogn comparisons in worst case... ?
one more thing is here same approach for upperbound ??
This is minimum for worst case ! yes there can not be less than this bound !
what abt upperbound ?
lower bound=best case=minimum worst case rt?
nope....lower bound=best case=minimum worst case rt    not true
nice @Debasish

Sometimes I am in doubt which one to choose best answer :p
haha..  this happen when more talented people are working on same thing :D
Between nice explanation Debashish :)  I can't believe you are  Mech Graduate :D
Just tell me one thing in the first place how are you making this  colourful drawings ? :p
Thanks @sreshtha

@pC picpick software
It seems a Win software  :(
Im Linux user :)
Anyway Thank you :)
Then use shuttle ..i use both.. little handicapped software, but have to deal with that.

Related questions

0 votes
2 answers
1
+3 votes
0 answers
2
asked in Algorithms by manu00x Veteran (14.9k points) 6 19 58 | 93 views


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
Top Users Oct 2017
  1. Arjun

    23398 Points

  2. Bikram

    17078 Points

  3. Habibkhan

    8280 Points

  4. srestha

    6300 Points

  5. Debashish Deka

    5438 Points

  6. jothee

    4978 Points

  7. Sachin Mittal 1

    4772 Points

  8. joshi_nitish

    4352 Points

  9. sushmita

    3970 Points

  10. Rishi yadav

    3804 Points


Recent Badges

Popular Question Sunil8860
Reader Rajesh Veeranki 2
Notable Question rahul sharma 5
Commentator Shivam Chauhan
Notable Question set2018
Nice Comment srestha
Notable Question set2018
Regular Shankar Jha
Popular Question Shubhanshu
Good Comment mcjoshi
27,325 questions
35,177 answers
84,123 comments
33,280 users