Suppose given an array $A[1..n]$ that contains $k$ distinct element, why the lower bound for sorting of this instance is $\Omega(n\log k)$?

I think according the decision tree the lower bound is $$log \frac{n!}{(n-k)!}.$$ But I can't achive $\Omega(n\log k)$.


Suppose that the number of array entries with each distinct element are $j_1, j_2, \ldots, j_k$. Note that $\sum_i j_i = n$.

Then the number of possible permutations of this array is:

$$\frac{n!}{j_1! j_2! \cdots j_k!}$$

We would like to find what distribution of keys will give us the largest number of permutations.

Glossing over quite a lot of rigour, the number of permutations is maximised in this case:

$$j_1 = \frac{n}{k}, \ldots, j_k = \frac{n}{k}$$

The number of permutations of this array is:


And so the minimum number of comparisons required to build a decision tree is:

$$\begin{eqnarray*}\log \frac{n!}{\left(\frac{n}{k}\right)!^k} & \approx & n \log n - k \frac{n}{k} \log \frac{n}{k} \\ & = & n \log k\end{eqnarray*}$$

By the way, the more general result is that the minimum number of comparisons required to sort an array of $n$ elements is $nH$ where $H$ is the zero-order entropy of the key distribution.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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