Number of nodes at given depth in binary tree

Question

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.

Answer 1

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