[racket] [Racket] computational complexity

On Sep 13, 2010, at 5:19 PM, Chris Stephenson <cs at cs.bilgi.edu.tr> wrote:

> ram access takes O (log n) time, where n is the RAM
> size supported by the word length. And if you have some kind of memory hierarchy (cache and RAM, or cache, RAM and disk) then things are definitely not really going to be O(1) when you might naively expect
> then to be, when you do some serious scaling.

Actually, since RAM exists in 3-dimensional space, the propagation delay to the memory cell you want is at least the cube root of the memory size; even log(n) is unrealistically optimistic.

Stephen Bloch
sbloch at adelphi.edu
>