Asymptotics of the complexity of interval search on a Boolean cube in the class of balanced trees

For a problem of interval search on the Boolean cube, we study the asymptotic behaviour of the average search time in the class of balanced tree circuits on sequences of positive integers $\{k_i\}$ under the assumption that $k_i$ are cardinalities of databases. We show that the asymptotic behaviour may differ on different sequences. We give a complete description of the class of possible behaviours.
This research was supported by the Russian Foundation for Basic Research, grant 01–01–00748.