È. È. Gasanov, A. M. Zubkov, N. V. Klykova, “The algorithm for identical object searching with bounded worst-case complexity and linear memory”, Diskr. Mat., 2016, Volume 28, Issue 2,Pages <nobr>3

The algorithm for identical object searching with bounded worst-case complexity and linear memory

È. È. Gasanov^a, A. M. Zubkov^b, N. V. Klykova^c

^a Lomonosov Moscow State University
^b Steklov Mathematical Institute of Russian Academy of Sciences, Moscow
^c PSC Lukoil

Abstract: We propose and investigate new algorithms permitting to find an identical object in the database using the number of operations not depending on the volume of the database. One algorithm requires memory size that depends linearly on the database volume in the average.

Keywords: key search, time complexity of algorithms, memory size.

UDC: 519.712.43

Received: 06.12.2015

DOI: 10.4213/dm1364