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