The actual time complexity of array access
Suppose we have an array holding n
bits of data. What is the time complexity of accessing the i
'th bit? I claim that it is in .
Firstly, there is a limit to how much information we can store in a given amount of space. A recent Stanford experiment achieved an information density of around 5 kilobytes per square nanometer. But the empirical value isn't important; let's say we can achieve an information density of ρ
.
Storing n
bits of information, then, requires an apparatus with a volume of at least n/ρ
. To minimize the average distance between the CPU and a unit of storage, we could use a spherical storage apparatus and place the CPU at its center. The volume a sphere is , so with a bit of algebra we get
.
Suppose our sphere is centered at the origin. Then the average distance is
,
where d
is the three dimensional Euclidian distance to a point from the origin. This comes out to be (3/4) r
. The integration is left as an exercise to the reader.
Information cannot travel faster than c
, the speed of light, which is a constant. So access time is linear with distance, which is linear with the radius of our storage apparatus. In particular,
.
Since and , it follows that
.
In other words, the time complexity of array access is lower bounded by the cubic root of the array's size.