# 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.