Why does an array give O(1) access to any index — what address computation makes element 5,000,000 one step away?

## The layout A static array is a single contiguous block of memory divided into cells of identical size. If the block starts at address `base` and each element occupies `element_size` bytes, then element `i` begins at: ``` address(i) = base + i * element_size ``` Nothing about this formula depends on the *contents* of the array or on how many elements precede `i`. Computing it is one multiplication and one addition — a fixed, tiny amount of work — and main memory (RAM, literally *random-access* memory) can then read or write that address directly. That is what O(1) random access means: the cost of reaching element `i` is a constant, independent of both `i` and the array's length. ## A worked example Suppose a market-data capture writes trade ticks as fixed-width 16-byte records: an 8-byte timestamp followed by an 8-byte price. Record 5,000,000 lives at `base + 5,000,000 × 16 = base + 80,000,000`. One multiply, one add, one read — the first 4,999,999 records are never touched. The same trick works on disk: a binary file of fixed-width records supports `seek(header + i * record_size)` to land on any record directly. Contrast a text file of variable-length lines: to find line 5,000,000 you must scan for newline characters, because no formula can tell you where a line starts when lines have different lengths. ## Why both preconditions matter **Contiguity.** If the elements were scattered around memory, knowing `i` would tell you nothing about where element `i` lives — you would need a lookup structure to find it, and consulting that structure is the very cost the array avoids. **Equal element size.** The multiplication `i * element_size` is only meaningful when every element occupies the same number of bytes. If elements varied in size, the position of element `i` would depend on the sizes of all elements before it — a running sum, which means either scanning or maintaining a separate offset table. Real systems that need arrays of variable-size things restore the invariant with indirection: store fixed-size *references* in the array and let each reference point to the variable-size data elsewhere. The address math stays O(1); you pay one extra memory hop to follow the reference. Managed runtimes broadly take this route for arrays of heap objects — the JVM and CPython, for instance, both lay out object arrays as same-size references rather than inlining the objects — while systems languages let you choose between inline values and pointers. The concept is the same everywhere; the default differs. ## The price: fixed capacity Contiguity has a cost. To guarantee that elements 0 through n−1 sit shoulder to shoulder, the block must be reserved as a whole, up front. That is why a static array has a fixed capacity: you cannot extend a block whose neighbouring memory may already belong to something else. Growing means allocating a new, larger block and copying — the machinery of dynamic arrays, which is a separate topic. The static array's deal is simple: give me my size at creation time, and I give you constant-time access to every cell forever. ## What changes at scale — and what doesn't At 10^9 elements the address computation is *exactly* as cheap as at 10 elements — the multiply and add do not grow. What scale changes is the memory budget: `capacity × element_size` is the footprint, so a billion 1-byte samples is about 1 GB while a billion 16-byte records is about 16 GB. The element-size choice, irrelevant to the asymptotic access cost, decides whether the array fits in RAM at all. Interviewers use this to check that you separate *time to reach an element* (constant) from *space to hold them all* (linear in count, scaled by element size). ## What this is not O(1) *indexed access* is not O(1) *search*. The formula takes you to a position, not to a value: finding which index holds a given price is still a linear scan unless the data is organized for searching. Conflating "arrays access in O(1)" with "arrays find in O(1)" is one of the most common junior slips in this area.