1
$\begingroup$

enter image description here

I saw this proposition on Sedgewick's lecture slides on QuickSort, and I've been wondering why the number of comparisons is linear in the case of a constant number of distinct keys. I tried to establish a linear upper bound but failed to find the appropriate linear lower bound. Here are my workings($N$ is the total number of keys): $$\begin{align} &-\sum\limits^{n}_{i=1}x_{i}\lg{\frac{x_i}{N}}\\&=\frac{1}{\ln2}\sum\limits^{n}_{i=1}x_{i}\ln{\frac{N}{x_i}} \\ & \leq \frac{1}{\ln2}\sum\limits^{n}_{i=1}\frac{N}{e}\ln{\frac{N}{\frac{N}{e}}} \quad(\text{by differentiation the maximum occurs when $x=N/e$}) \\ & =\frac{N}{e\ln2}\sum\limits^{n}_{i=1}\ln{e} \\ & =\frac{n}{e\ln2}N \end{align}$$ When $n$ is constant, it's linear in $N$. But I failed to find a similar lower bound.

I also found another result given by Sedgewick using entropy. The number of compares can be written as $NH$, where $H=-\sum\limits^{n}_{i=1}\frac{x_i}{N}\lg{\frac{x_i}{N}}$. I'm not familiar with information theory, but does this mean that when $n$ is constant, the entropy can be considered constant, so the number of compares is linear?

$\endgroup$
8
  • $\begingroup$ Consider what happens if $x_1=\cdots=x_{n-1}=1$ to see what kind of lower bound you can expect. $\endgroup$ Commented Feb 10, 2022 at 7:28
  • $\begingroup$ @YuvalFilmus Then the expression becomes$(n-1)\lg{N}+(N-n+1)\lg{\frac{N}{N-n+1}}$ and we can argue that $\lg{\frac{N}{N-n+1}}$ is constant when $N$ is much larger than $n$? But how can we be sure that this is the minimum of the expression? I mean, can we simply say that the expression is $\geq{(n-1)\lg{N}+(N-n+1)\lg{\frac{N}{N-n+1}}}$? $\endgroup$ Commented Feb 10, 2022 at 8:13
  • $\begingroup$ You can estimate your expression using the Taylor expansion of $\log(1+x)$. As for why it is the minimum, it should follow from convexity/concavity. $\endgroup$ Commented Feb 10, 2022 at 11:13
  • $\begingroup$ @YuvalFilmus Thanks for your comment. I managed to prove that $\lg{\frac{N}{N-n+1}}$ is approximately constant by the Taylor expansion. As regards the minimum, did you mean to consider the convexity/concavity of $-\sum\limits^{n}_{i=1}x_{i}\lg{\frac{x_i}{N}}$? Could you give some hints because I don't know where to start? $\endgroup$ Commented Feb 10, 2022 at 11:50
  • $\begingroup$ It's convexity/concavity of the function $-x\log x$. $\endgroup$ Commented Feb 10, 2022 at 12:46

1 Answer 1

1
$\begingroup$

You are missing an easy approach.

The case of $n=1$ is trivial. No comparison is needed.

Otherwise, let $n\ge2$. Suppose we have sorted $N$ keys with $m$ comparisons. For each comparison, connect two keys involved with an edge, considering each key as a node. With $m$ comparisons, we obtain a graph of $N$ keys. That graph must be connected; otherwise, we cannot sort the keys that belong to different connected components. That means there are at least $N-1$ edges in the graph, i.e., there must have been at least $N-1$ comparisons. This lower bound of $N-1$ comparisons for general cases (which include the worst case of course) can be the linear lower bound you want.

The lower bound of the worst case could be refined to be something like $\displaystyle\Theta(nN)$ for some appropriate meaning of $\Theta$ for two variables $n$ and $N$. However, it is probably another question to prove that.

$\endgroup$
6
  • $\begingroup$ Thanks for your answer! I would like to ask a few questions. i) for the case of $n=1$ do you mean that no comparison is needed because it's already sorted? But is there any compared-based sorting algorithm that uses no comparison when we don't know $n=1$ in advance? ii) If I understood it, to prove $\Theta(nN)$ we need to find a lower bound for the original expression just like what I did for its upper bound? $\endgroup$ Commented Feb 10, 2022 at 3:01
  • $\begingroup$ i) Yes, since $n=1$ means all keys are the same. If we don't know $n=1$ in advance, at least one comparison is needed to sort the given list unless $N=1$. ii) In the answer I assume all we know is the number of distinct keys is $n$ and $n>1$ (i.e., we do not know the frequency of each keys except the corner case when $n=N$). Yes, to prove $\Theta(nN)$ as a lower bound for the worst case, we can show that $$\max_{x_1+x_2 +\cdots+x_n=N}\log_2\left(\frac{N!}{x_1!x_2!\cdots x_n!}\right)\ge \frac{nN}{2e\ln 2}$$ when $N/n$ are large enough. That inequality, in fact, not hard to prove. $\endgroup$
    – John L.
    Commented Feb 10, 2022 at 4:17
  • $\begingroup$ Thanks for your clarification. i) "At least one comparison is needed to sort the array" if we don't know $n=1$ still seems hard to me, is it a conservative lower bound, or how can an algorithm detect this case in only one comparison? ii) I'm a little confused by the "max" operator in your expression. Does it mean the maximum of the expression is at least that much? But if we are looking for the maximum, shouldn't it occur when each $x_i=1$? Then the expression turns into $\frac{N\log_2{N}}{\ln2}$, but I can't find a way to derive the desired inequality. Thanks for your patience. $\endgroup$ Commented Feb 10, 2022 at 7:00
  • $\begingroup$ Or did you mean that we need to prove that the minimum of that expression(when the denominator is biggest) is at least that much? $\endgroup$ Commented Feb 10, 2022 at 7:18
  • $\begingroup$ i) the case with $n=1$ is trivial. There is really not much to talk about. I believe you know what you were talking about. I know what I was talking about. Even if there have been misunderstanding between us, let us just ignore this trivial case. ii) Here is the complete statement: Given any positive integers $n>1$ and $N$, there exists a constant $c$ such that if $N/n > c$, then for all positive integers$x_1, x_2, \cdots, x_n$ such that their sum is $N$, we have $$\log_2\left(\frac{N!}{x_1!x_2!\cdots x_n!}\right)\ge \frac{nN}{2e\ln 2}.$$ $\endgroup$
    – John L.
    Commented Feb 10, 2022 at 7:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.