[r6rs-discuss] Proposed features for small Scheme, part 4F: more symmetry

[Brian Mastenbrook]

On Nov 5, 2009, at 3:32 PM, John Cowan wrote:

> However, so-called RAM is no longer random access in the sense of O(1)
> access time; it is now O(N) (though with a much smaller constant than
> is required for linked access) unless the vector is entirely within a
> CPU cache.

It is most definitely not O(n). Even if vector access never touches  
CPU cache, accessing a particular page in memory is not O(n) in the  
page number. At worst, page fragmentation will lead to O(lg n) access  
time for vector elements, but in practice everybody ignores this  
factor as the constant on it is very, very small.

--
Brian Mastenbrook
brian at mastenbrook.net
http://brian.mastenbrook.net/