|
A lower bound on the time complexity of an integer problem on the uniqueness of elements
L. V. Nosov
Abstract:
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.
Received: 11.09.1989
Citation:
L. V. Nosov, “A lower bound on the time complexity of an integer problem on the uniqueness of elements”, Diskr. Mat., 3:3 (1991), 31–34; Discrete Math. Appl., 2:3 (1992), 319–323
Linking options:
https://www.mathnet.ru/eng/dm801 https://www.mathnet.ru/eng/dm/v3/i3/p31
|
Statistics & downloads: |
Abstract page: | 520 | Full-text PDF : | 97 | First page: | 1 |
|