Average complexity of searching for identical objects in random nonuniform databases

DOI10.1515/DMA.2011.023MaRDI QIDQ2889732zbMATH OpenOpenAlexFDO

Authors N. S. Kucherenko

Publication date 8 June 2012

Published in Discrete Mathematics and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1515/dma.2011.023

zbMATH Keywords

average complexity of optimal algorithms

Mathematics Subject Classification ID

Database theory (68P15) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Approximation algorithms (68W25)

Recommendations

• The algorithm for identical object searching with bounded worst-case complexity and linear memory
• scientific article; zbMATH DE number 999544
• A constant, in the worst case, algorithm to search for identical objects
• scientific article; zbMATH DE number 4201596
• Dynamic databases with optimal in order time complexity

Cites work

• A New Algorithm for Minimum Cost Binary Trees
• Optimum binary search trees

Cited in

(6)

• Information storage and search complexity theory
• scientific article; zbMATH DE number 999544 (Why is no real title available?)
• The algorithm for identical object searching with bounded worst-case complexity and linear memory
• VERIFIER-BASED ALGORITHM FOR UNSORTED DATABASE SEARCH PROBLEM
• Average-Case Lower Bounds for Searching
• A constant, in the worst case, algorithm to search for identical objects

This page was built for publication: Average complexity of searching for identical objects in random nonuniform databases

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2889732)