A nonlinear lower bound for random-access machines under logarithmic cost
Arnold Schönhage · Journal of the ACM · 1988
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 .