Geodesic
Asymptotics of the complexity of interval search on a Boolean cube in the class of balanced trees
Diskretnaya Matematika, Tome 16 (2004) no. 4, pp. 65-78 
T. D. Blaivas. Asymptotics of the complexity of interval search on a Boolean cube in the class of balanced trees. Diskretnaya Matematika, Tome 16 (2004) no. 4, pp. 65-78. http://geodesic.mathdoc.fr/item/DM_2004_16_4_a6/
@article{DM_2004_16_4_a6,
     author = {T. D. Blaivas},
     title = {Asymptotics of the complexity of interval search on a {Boolean} cube in the class of balanced trees},
     journal = {Diskretnaya Matematika},
     pages = {65--78},
     year = {2004},
     volume = {16},
     number = {4},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2004_16_4_a6/}
}
TY  - JOUR
AU  - T. D. Blaivas
TI  - Asymptotics of the complexity of interval search on a Boolean cube in the class of balanced trees
JO  - Diskretnaya Matematika
PY  - 2004
SP  - 65
EP  - 78
VL  - 16
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/DM_2004_16_4_a6/
LA  - ru
ID  - DM_2004_16_4_a6
ER  - 
%0 Journal Article
%A T. D. Blaivas
%T Asymptotics of the complexity of interval search on a Boolean cube in the class of balanced trees
%J Diskretnaya Matematika
%D 2004
%P 65-78
%V 16
%N 4
%U http://geodesic.mathdoc.fr/item/DM_2004_16_4_a6/
%G ru
%F DM_2004_16_4_a6

Voir la notice de l'article provenant de la source Math-Net.Ru

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.

[1] Blaivas T. D., “Optimalnoe reshenie zadachi intervalnogo poiska na bulevom kube v klasse sbalansirovannykh drevovidnykh skhem”, Intellektualnye sistemy (to appear)

[2] Blaivas T. D., “Reshenie zadachi intervalnogo poiska na bulevom kube”, Tezisy dokladov XIII Mezhdunarodnoi konferentsii “Problemy teoreticheskoi kibernetiki”, Kazan, 2002, 22

[3] Gasanov E. E., Kudryavtsev V. B., Teoriya khraneniya i poiska informatsii, Fizmatlit, Moskva, 2002 | Zbl