Practically for a given strategy, the difficulty lies in computing the variance of C n , which is the sum of the variances of the X i 's. The most commonly used strategies, linear search and binary search, satisfy the condition of Lemma 1. There exists tree-growing search strategies which are not normal. To ensure normality, some further conditions, which are presented in the next section, are required on the decision trees of the search strategy. 2 Normality of consistent strategies This section identifies a subclass of tree-growing strategies, the consistent strategies, which are proved to be normal.
All consistent strategies are normal.
The proof of this theorem relies on three properties of search strategies decision trees that ensure the sufficient condition for normality stated in Lemma 1. T i has at least one external node on each unsaturated level. The sufficient condition for normality stated in Lemma 1 holds true for some families of tree-growing search strategies that are not consistent. More generally, one can exhibit different conditions on search strategies, that lead to normality by showing that the heights of the decision trees grow at a steady rate. On tree-growing search strategies.