Average-Case Lower Bounds for Searching

DOI10.1137/0217066MaRDI QIDQ3813304zbMATH OpenOpenAlexFDO

Authors Colin McDiarmid

Publication date 1988

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/0217066

zbMATH Keywords

average caseinformationLower boundssearchingsortingtrade-offsuncertainty

Mathematics Subject Classification ID

Combinatorial probability (60C05) Searching and sorting (68P10)

Recommendations

• Lower bounds on fast searching
• scientific article; zbMATH DE number 1535253
• On the complexity of searching in trees: average-case minimization
• scientific article; zbMATH DE number 1334210
• Combinatorial Pattern Matching
• Average-case analysis of approximate trie search
• Improved approximation algorithms for the average-case tree searching problem
• scientific article; zbMATH DE number 1263218
• Average complexity of searching for identical objects in random nonuniform databases
• scientific article; zbMATH DE number 1445326

Cited in

(10)

• A tradeoff between search and update in dictionaries
• Searching Semisorted Tables
• The average complexity of depth-first search with backtracking and cutoff
• scientific article; zbMATH DE number 1263218 (Why is no real title available?)
• scientific article; zbMATH DE number 637529 (Why is no real title available?)
• scientific article; zbMATH DE number 1535253 (Why is no real title available?)
• Improved approximation algorithms for the average-case tree searching problem
• Average-case lower bounds for the plurality problem
• On the probabilistic worst-case time of ``find
• Average-case analysis of best-first search in two representative directed acyclic graphs

This page was built for publication: Average-Case Lower Bounds for Searching

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