A nonlinear lower bound for random-access machines under logarithmic cost

DOI10.1145/44483.44492zbMath0661.68040OpenAlexW2040439439MaRDI QIDQ3811705

Arnold Schönhage

Publication date: 1988

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/44483.44492

zbMATH Keywords

complexityrandom-access machinelogarithmic costswitching sequences

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items (3)

Invariance properties of RAMs and linear time ⋮ The complexity of on-line simulations between multidimensional turing machines and random access machines ⋮ Sorting, linear time and the satisfiability problem

This page was built for publication: A nonlinear lower bound for random-access machines under logarithmic cost