On pointers versus addresses
Amir M. Ben-Amram, Zvi Galil · Journal of the ACM · 1992
What is the cost of random access to memory?This fundamental problem M addressed by studying the simulation of random addressing by a machine that lacks it, a "pointer machine.'"The problem is formulated in the context of high-level computational models, allowing the use of a data type of our choice, A RAM program of time tand space s can be simulated m 0( f log .s)time using a tree.To enable a lower-bound proof, we formalize a notion of incompressibility for general data types.The main theorem states that for all incompressible data types an Ll( f log s) lower bound holds.Incompressibility trivially holds for strings, but is harder to prove for a powerful data type.Incompressibility is proved for the real numbers with a set of primitives that includes all functions that are continuous except on a countable closed set.This may be the richest set of operations considered m a lower-bound proof.It is also shown that the integers with arithmetic +, -, x and [ .x/2~,any Boolean operations, and left shift are incompressible.Tbe situation is reversed once right shift is allowed.