This article is cited in 2 papers

Average complexity of searching for identical objects in random nonuniform databases

N. S. Kucherenko


Abstract: In this paper we study the average complexity of optimal algorithms solving the problem of searching for identical objects (PSIO) for random databases. We describe and investigate classes of PSIOs for which the average complexity as a function of the database volume grows logarithmically. For such classes of problems we find exact asymptotics of the complexity. We also study the case where the complexity of the optimal algorithm averaged over the class of problems is bounded and construct a class of PSIOs such that the average complexity of the optimal algorithm is an unbounded function growing slower than the logarithm.

UDC: 519.2

Received: 13.10.2010
Revised: 07.02.2011

DOI: 10.4213/dm1148

 English version: Discrete Mathematics and Applications, 2011, 21:3, 345–379

Bibliographic databases:

• 
• 
•