A note on the best-case complexity

DOI10.1016/0020-0190(89)90131-2zbMath0672.68019OpenAlexW2012736284MaRDI QIDQ1120281

Sheila A. Greibach, José D. P. Rolim

Publication date: 1989

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(89)90131-2

zbMATH Keywords

complexity theoryalmost everywhereinfinitely oftenbest-caseworst- case

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15)

Related Items (2)

On the IO-complexity and approximation languages ⋮ On the polynomial IO-complexity

Cites Work

• Relationships between nondeterministic and deterministic tape complexities
• On Almost Everywhere Complex Recursive Functions
• Relativization of the Theory of Computational Complexity
• On the Computational Complexity of Algorithms
• A Machine-Independent Theory of the Complexity of Recursive Functions

This page was built for publication: A note on the best-case complexity