NORMALITY OF TREE-GROWING SEARCH STRATEGIES

We study the class of tree-growing search strategies introduced by Len t and Mahmoud, searches for which data are stored in a deterministic s equence of tree structures (e.g., linear search in forward order). Spe cifically, we study the conditions under which the number of compariso ns needed to sort a sequence of randomly ordered numbers is asymptotic ally normal. Our main result is a sufficient condition for normality i n terms of the growth rate of tree height alone; this condition is eas ily computed and is satisfied by all standard deterministic search str ategies. We also give some examples of normal search strategies with s urprisingly small variance, in particular, much smaller than is possib le for the class of consistent strategies that are the focus of the wo rk by Lent and Mahmoud.