The asymptotic behaviour of the complexity of the interval search on the Boolean cube in the class of balanced trees
T. D. Blaivas · Discrete Mathematics and Applications · 2004
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.