[racket] [Racket] computational complexity

From: Stephen Bloch (sbloch at adelphi.edu)
Date: Mon Sep 13 18:12:34 EDT 2010

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

Posted on the users mailing list.