# Number of nodes at given depth in binary tree

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.

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.$$
• In your text, $n$ is the input length, and $k$ is an arbitrary constant. – Yuval Filmus Dec 13 '20 at 20:02