Decision tree model

The decision tree model describes an algorithm as a rooted tree. Each inner node asks one query about the input, each branch is one answer, and each leaf gives the output. The cost of the algorithm on an input is the number of queries on the path that the input follows, and the cost of the algorithm is the height of the tree, the largest number of queries on any path. Only queries cost: all other work is free, so a lower bound in this model holds for every algorithm that learns about its input through these queries, however fast its other steps are.

The machine

Fix a set $X$ of inputs, a set $Y$ of outputs and a function $f : X \to Y$ to compute. Fix a set $Q$ of allowed queries. A query is a function $q : X \to A_q$ where $A_q$ is a finite set of answers. In a binary tree, $|A_q| = 2$.

A decision tree over $Q$ is a rooted tree with these parts.

• Each inner node $v$ has a query $q_v \in Q$ and, for each answer $a \in A_{q_v}$, at most one child $v_a$.
• Each leaf has a label in $Y$.

The tree runs on an input $x \in X$ as follows. It starts at the root. At an inner node $v$ it computes $a = q_v(x)$ and moves to the child $v_a$. At a leaf it outputs the label of the leaf. The tree computes $f$ when, for each $x \in X$, the run on $x$ reaches a child that exists and ends with the output $f(x)$.

The tree is a fixed object, not a program with a loop. It is built for one problem size. So the model is non-uniform: an algorithm for all sizes is a family of trees, one for each size.

Three common choices of $Q$:

• Comparison trees. The input is a sequence $x_1, \dots, x_n$ of keys, and a query is "$x_i < x_j$?" with two answers, or a three-way comparison of $x_i$ and $x_j$ with answers less, equal and greater. This is the comparison model.
• Boolean decision trees. The input is a bit string $x \in \{0,1\}^n$, and a query reads one bit $x_i$.
• Algebraic trees. A query asks for the sign of a polynomial of the inputs. See algebraic decision trees, linear decision trees and algebraic computation trees.

What it counts

The depth of a leaf is the number of edges from the root to the leaf. The height of a tree is the largest depth of a leaf. Let $\mathrm{D}(f)$ be the least height of a decision tree over $Q$ that computes $f$. This is the worst-case cost of $f$ in the model: some input needs $\mathrm{D}(f)$ queries, and no algorithm of the model does better on its worst input.

For a probability distribution $\mu$ on $X$, the average cost of a tree is $\sum_{x \in X} \mu(x) \cdot \mathrm{depth}(\text{leaf reached by } x)$. A randomized algorithm is a probability distribution over trees. Its expected cost on an input is the average over this distribution. The randomized cost of the algorithm is the largest expected cost over all inputs $x \in X$. See the Yao minimax principle.

The model does not count the size of the tree, the memory, or any work between queries.

Relation to other models

• The comparison model is the decision tree model with $Q$ equal to the comparisons of two input keys. A deterministic comparison-based algorithm, such as merge sort, gives one tree for each input size (a randomized one gives a distribution over such trees), and the number of comparisons that it makes on an input is the length of the path of that input.
• A branching program is a decision tree in which different paths can meet again, so it is a directed acyclic graph. A decision tree is a branching program of which the graph is a tree. The graph form can be much smaller.
• The cell-probe model and the bit-probe model are decision trees in which a query reads one cell or one bit of a data structure.
• The model gives only lower bounds that hold for algorithms that use the queries of $Q$. An algorithm with other operations, such as the arithmetic of counting sort or radix sort, is not a tree over comparisons and can be faster.

Known results in the model

The counting lemma

Lemma 1. A tree in which each inner node has at most $k$ children and every leaf has depth at most $h$ has at most $k^h$ leaves.

Proof. By induction on $h$. If $h = 0$, the tree is a single leaf, and $k^0 = 1$. Let $h \ge 1$ and suppose the claim holds for $h - 1$. The root is an inner node or a leaf. If it is a leaf, the tree has 1 leaf, and $1 \le k^h$ when $k \ge 1$. Otherwise the root has at most $k$ subtrees, and each is a tree of which every leaf has depth at most $h - 1$ in the subtree. By the induction hypothesis each subtree has at most $k^{h-1}$ leaves. So the tree has at most $k \cdot k^{h-1} = k^h$ leaves. ∎

Corollary 2 (counting bound). This is the information-theoretic bound, a counting argument on the leaves, and it is the base of the decision tree method for lower bounds. Let a decision tree with at most $k$ answers for each query compute $f : X \to Y$. Let $h$ be its height. Then $k^h \ge |f(X)|$, so

Proof. For each $y \in f(X)$ there is an input $x$ with $f(x) = y$. The run on $x$ ends at a leaf with label $y$. So the labels of the leaves cover $f(X)$, and the tree has at least $|f(X)|$ leaves. By Lemma 1 the tree has at most $k^h$ leaves. So $k^h \ge |f(X)|$. Take $\log_k$ on both sides. The height $h$ is an integer, so $h \ge \lceil \log_k |f(X)| \rceil$. ∎

Sorting

The sorting problem asks for the keys in order. Take the inputs to be the $n!$ sequences of $n$ distinct keys, written as permutations of $\{1, \dots, n\}$. The output is the permutation that sorts the input, so the outputs of two different inputs are different. Comparisons of distinct keys have two answers, "less" and "greater", so $k = 2$.

Theorem 3. Each comparison tree that sorts $n$ distinct keys has height at least $\lceil \lg(n!) \rceil$. Also $\lg(n!) \ge n \lg n - n \lg e$, so the height is $\Omega(n \log n)$.

Proof. The function $f$ maps each input to its sorting permutation, so $|f(X)| = n!$. Corollary 2 with $k = 2$ gives $h \ge \lceil \lg(n!) \rceil$. For the second claim, $e^n = \sum_{j \ge 0} n^j / j! \ge n^n / n!$, because the term $j = n$ is one term of a sum of positive terms. So $n! \ge (n/e)^n$, and $\lg(n!) \ge n \lg n - n \lg e$ with $\lg e \approx 1.4427$. For $n \ge 8$ this is at least $n \lg n - 1.45 n \ge (n \lg n)/2$, because $\lg n \ge 3$ gives $0.5 \lg n \ge 1.5 > 1.45$. ∎

A three-way comparison tree has three children for each node, and the "equal" child is never reached on distinct keys. So removing it leaves a tree with two children, and the same bound holds.

The table shows the bound for small $n$. The last column is the least worst-case number of comparisons of any comparison sort, as Knuth tabulates it in Section 5.3.1.

$n$	$n!$	$\lg(n!)$	$\lceil \lg(n!) \rceil$	least worst case
3	6	2.585	3	3
4	24	4.585	5	5
5	120	6.907	7	7
6	720	9.492	10	10
10	3628800	21.791	22	22
12	479001600	28.835	29	30

The bound is tight for $n \le 11$, and it is not tight for $n = 12$: the count argument only counts leaves and does not say that a tree with $n!$ leaves of nearly equal depth exists. The Ford and Johnson algorithm reaches the values of the last column. For large $n$ the bound is tight up to the linear term: merge sort uses at most $n \lceil \lg n \rceil - 2^{\lceil \lg n \rceil} + 1$ comparisons, which is $n \lg n + O(n)$. See the comparison sort lower bound.

Example, $n = 3$. Call the keys $a, b, c$. The tree below sorts them with at most 3 comparisons. Each line is a node. Indentation shows the depth.

a < b ?
  yes: b < c ?
         yes: output a b c
         no:  a < c ?
                yes: output a c b
                no:  output c a b
  no:  b < c ?
         yes: a < c ?
                yes: output b a c
                no:  output b c a
         no:  output c b a

The tree has 6 leaves, two at depth 2 and four at depth 3. The height is 3, which is $\lceil \lg 6 \rceil$. No tree of height 2 exists, because a binary tree of height 2 has at most 4 leaves.

The average depth

Lemma 4. A binary tree in which each inner node has exactly two children and that has $L \ge 1$ leaves has leaf depths that add up to at least $L \lg L$.

Proof. By strong induction on $L$. For $L = 1$ the tree is one leaf of depth 0, and $1 \cdot \lg 1 = 0$. Let $L \ge 2$. The root has two subtrees with $L_1$ and $L_2$ leaves, where $L_1, L_2 \ge 1$ and $L_1 + L_2 = L$. Each leaf is one level deeper in the whole tree than in its subtree. Let $E(\cdot)$ be the sum of the leaf depths. Then $E = L + E_1 + E_2$. By the induction hypothesis $E \ge L + L_1 \lg L_1 + L_2 \lg L_2$. The function $g(x) = x \lg x$ is convex for $x > 0$, because $g''(x) = 1/(x \ln 2) > 0$. So $g(L_1) + g(L_2) \ge 2 g(L/2) = L \lg(L/2) = L \lg L - L$. Hence $E \ge L + L \lg L - L = L \lg L$. ∎

Theorem 5. Let a comparison tree sort $n$ distinct keys. If the input is a uniformly random permutation, the expected number of comparisons is at least $\lg(n!)$.

Proof. Each input reaches one leaf. Two different inputs have different sorted outputs, so they reach different leaves. So exactly $n!$ leaves are reached, and each is reached by one input. The average depth is $\frac{1}{n!}$ times the sum of the depths of these leaves. Delete all nodes that no input reaches. Some inner nodes now have one child. Remove each such node and join its parent to its child. This step does not increase the depth of a leaf. The result is a tree with $n!$ leaves in which each inner node has two children. By Lemma 4 its leaf depths add up to at least $n! \lg(n!)$. The depths in the original tree are at least as large. So the average is at least $\lg(n!)$. ∎

Two consequences follow. First, the bound of Theorem 3 holds for the average case too: an average of at least $\lg(n!)$ gives a worst case of at least $\lg(n!)$. Second, it holds for randomized algorithms. A randomized comparison sort is a distribution over trees, each of which sorts. By Theorem 5, on a uniformly random input each tree has an average of at least $\lg(n!)$. So the average over the distribution is at least $\lg(n!)$, and some input has expected cost at least $\lg(n!)$.

Search in a sorted array

The array $A[1] < A[2] < \dots < A[n]$ is known to be sorted. The order of the array is known, so a comparison of two array entries gives no information. A query compares $x$ with one entry $A[i]$, with the answers less, equal and greater. The algorithm must output an index $i$ with $A[i] = x$, or the word "absent".

Theorem 6. Each comparison tree that solves this problem on all inputs has height at least $\lceil \lg(n+1) \rceil$.

Proof. Use the array $A[i] = 2i$ and consider the $n$ inputs $x = 2i$. For each $i$, the run on $x = 2i$ passes through a node that compares $x$ with $A[i]$. Suppose not, for some $i$. The run on $x = 2i$ ends at a leaf. This leaf must say "found at $i$". Now take $x' = 2i + 1$. Each comparison on the path is with some $A[j]$ with $j \ne i$, and $x$ and $x'$ give the same answer: both are greater than $A[j]$ for $j < i$, and both are less than $A[j]$ for $j > i$. So the run on $x'$ ends at the same leaf. But $x'$ is not in the array, so the answer is wrong. This is a contradiction.

So there are at least $n$ nodes in the tree, one for each index, and they are different nodes. Let the node for $i$ be the first node on the run for $x = 2i$ that compares $x$ with $A[i]$. Every earlier answer on this run is "less" or "greater", because "equal" can occur only when $x$ is compared with $A[i]$. The nodes that are reached by "less" and "greater" answers only are at most $2^d$ at depth $d$. The $n$ nodes are inner nodes, so their depths are in $0, \dots, h - 1$. Hence $n \le 1 + 2 + \dots + 2^{h-1} = 2^h - 1$ and $h \ge \lg(n+1)$. The height is an integer. ∎

Binary search makes at most $\lfloor \lg n \rfloor + 1 = \lceil \lg(n+1) \rceil$ probes. For $n = 7$ both numbers are 3, and for $n = 8$ both are 4. So the bound is tight for each $n$. See sorted search lower bound and search in a sorted array.

A bound that counting does not give

Counting needs many outputs. The function $f : \{0,1\}^n \to \{0,1\}$ has two outputs, so Corollary 2 gives only $h \ge 1$. For the parity function, a different argument gives a much better bound.

Theorem 7. Every Boolean decision tree that computes the parity $x_1 \oplus \dots \oplus x_n$ has height at least $n$, and some tree has height $n$. So $\mathrm{D}(\text{parity}) = n$.

Proof. The tree that reads $x_1, \dots, x_n$ in order has height $n$. Now take any tree of height less than $n$. Take a leaf and an input $x$ that reaches it. The path has fewer than $n$ queries, so some index $i$ is not queried on it. Let $x'$ be $x$ with bit $i$ changed. The run on $x'$ gives the same answers to the same queries, so it reaches the same leaf. The two inputs have different parity but the same output. So the tree is wrong. ∎

This is an adversary argument: the adversary answers each query and keeps one free bit until the end.

References

1. Cormen, Leiserson, Rivest and Stein, Introduction to Algorithms, fourth edition, Section 8.1
2. Donald E. Knuth, The Art of Computer Programming, Volume 3, second edition, Section 5.3.1
3. Robert Sedgewick and Kevin Wayne, Algorithms, fourth edition, Section 2.2, Proposition I