2
$\begingroup$

Show that there is no comparison sort whose running time is linear for at least half of the $n!$ inputs of length $n$. What about a fraction of $1/n$ of the inputs of length $n$? What about a fraction of $1/2^n$?

  • The running time of a specific input is linear if the corresponding leaf node is within a linear distance from the root. Considering a binary tree, the maximum number of nodes within a linear distance from the root is $2^{kn+1}-1$.

How $2^{kn+1}-1$ was reached? just I need an intuitive idea not a proof. this is my notes not an homework or exercises. $k$ and $n$ not defined on it context.

$\endgroup$
2
2
$\begingroup$

Intuitively, the maximum number of leaves at distance at most $d$ from the root is obtained when all of these leaves are at distance exactly $d$ from the root. Since there are at most $2^d$ nodes at distance exactly $d$ from the root, this suggests that the maximum number of leaves at distance at most $d$ from the root is $2^d$.

We can easily prove this bound formally using Kraft's inequality, which states that $$ \sum_{\ell} 2^{-d(\ell)} \leq 1, $$ where $\ell$ goes over all leaves, and $d(\ell)$ is the distance of $\ell$ from the root. Kraft's inequality implies that $$ 1 \geq \sum_{\ell\colon d(\ell) \leq d} 2^{-d(\ell)} \geq \sum_{\ell\colon d(\ell) \leq d} 2^{-d},$$ from which it immediately follows that there are at most $2^d$ leaves at distance at most $d$ from the root.


The text you quote is less sophisticated. It is bounding the number of leaves at distance at most $d$ from the root by the number of nodes at distance at most $d$ from the root. Since there are at most $2^e$ nodes at distance exactly $e$ from the root, it follows that the number of nodes at distance at most $d$ from the root is bounded by $$ \sum_{e=0}^d 2^e = 2^{d+1} - 1. $$

$\endgroup$
1
  • $\begingroup$ In your text, $n$ is the input length, and $k$ is an arbitrary constant. $\endgroup$ – Yuval Filmus Dec 13 '20 at 20:02

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.