Geodesic
A lower bound on the time complexity of an integer problem on the uniqueness of elements
Diskretnaya Matematika, Tome 3 (1991) no. 3, pp. 31-34 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

We consider an integer problem on the uniqueness of elements which we formulate as follows: Check whether there exists among $n$ given integers at least one pair equal to each other. We prove that $\Omega (n\log n)$ is the lower bound on the time complexity of this problem in a model of a linear solution tree. We obtain lower bounds on the time complexity of several geometric problems to which it reduces. 
@article{DM_1991_3_3_a2,
     author = {L. V. Nosov},
     title = {A~lower bound on the time complexity of an integer problem on the uniqueness of elements},
     journal = {Diskretnaya Matematika},
     pages = {31--34},
     year = {1991},
     volume = {3},
     number = {3},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_1991_3_3_a2/}
}
TY  - JOUR
AU  - L. V. Nosov
TI  - A lower bound on the time complexity of an integer problem on the uniqueness of elements
JO  - Diskretnaya Matematika
PY  - 1991
SP  - 31
EP  - 34
VL  - 3
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/DM_1991_3_3_a2/
LA  - ru
ID  - DM_1991_3_3_a2
ER  - 
%0 Journal Article
%A L. V. Nosov
%T A lower bound on the time complexity of an integer problem on the uniqueness of elements
%J Diskretnaya Matematika
%D 1991
%P 31-34
%V 3
%N 3
%U http://geodesic.mathdoc.fr/item/DM_1991_3_3_a2/
%G ru
%F DM_1991_3_3_a2
L. V. Nosov. A lower bound on the time complexity of an integer problem on the uniqueness of elements. Diskretnaya Matematika, Tome 3 (1991) no. 3, pp. 31-34. http://geodesic.mathdoc.fr/item/DM_1991_3_3_a2/