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

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

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

Full text

Pdf (511 KB)

Source

Journal of the ACM (JACM) archive
Volume 35 , Issue 3 (July 1988) table of contents

Pages: 748 - 754

Year of Publication: 1988

ISSN:0004-5411

Author

Arnold Schönhage

Univ. Tu¨bingen, Federal Republic of Germany

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 6, Downloads (12 Months): 23, Citation Count: 1

Additional Information:

abstract references cited by index terms collaborative colleagues peer to peer

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTex EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/44483.44492 What is a DOI?

ABSTRACT

For on-line random-access machines under logarithmic cost, the simple task of storing arbitrary binary inputs has nonlinear complexity. Even if all kinds of powerful internal operations are admitted and reading of storage locations is free of charge, just successively changing the storage contents for properly storing arbitrary n-bit inputs requires an average cost of order n · log*n.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
	2	KATAJAINEN, J., VAN LEEUWEN, J., AND PENTTONEN, M.O. Fast simulation of Turing machines by random access machines. Rep. 837. Univ. of Turku, Finland, Oct. 1985.
	3	SCrlONHAGE, A. Storage modification machines. SIAM J. Comput. 9 (1980), 490-508.