Асимптотика сложности интервального поиска на булевом кубе в классе сбалансированных деревьев

Для задачи интервального поиска на булевом кубе исследуется асимптотическое поведение среднего времени поиска в классе сбалансированных древовидных схем на последовательностях натуральных чисел $\{k_i\}$ в предположении, что $k_i$ — мощность баз данных, $i=1,2,\dots$ . Показано, что для разных последовательностей асимптотическое поведение может быть разным. Полностью описан класс возможных асимптотических поведений.
Работа выполнена при поддержке Российского фонда фундаментальных исследований, проект 01–01–00748.