[r6rs-discuss] Proposed features for small Scheme, part 4F: more symmetry
Arthur A. Gleckler
scheme at speechcode.com
Thu Nov 5 16:43:51 EST 2009
> 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.
This is misleading. Accessing a particular element is not O(N) if N
is the length of the vector. It's still O(1), but with a much larger
constant. In other words, access time is not proportional to the
length of the vector.
More information about the r6rs-discuss