Algorithms and data structures · Introductory

Arrays: why indexed access is constant time

Connect contiguous storage and address arithmetic to fast indexing, insertion costs, and dynamic-array growth.

Ask Logeia about this articleTry the three questionsReview your answers

Updated

On this page
  1. Compute an address instead of following links
  2. Trace an insertion
  3. Separate length from capacity
  4. Choose an array for the operations you need
  5. Ask Logeia about this articleCheck your understanding

Compute an address instead of following links

For an array of fixed-size elements, the address of element i is the base address plus i multiplied by the element size. If elements occupy four bytes and indexing starts at zero, element three begins twelve bytes after the base. This is the reason indexed access is constant time in the usual RAM model. An array of object references stores those references contiguously; the objects they point to can still be scattered elsewhere in memory.

Trace an insertion

Start with [10, 20, 30, 40] and insert 15 at index one while preserving order. The values 20, 30, and 40 must move one position to the right before 15 is stored. Spare capacity prevents reallocation but does not eliminate these shifts. An insertion near the front of a length-n array therefore takes linear time. If order is irrelevant, deleting an item by moving the last item into its slot can avoid shifting, but it changes the sequence.

Separate length from capacity

A dynamic array records both its current length and its allocated capacity. Growing a full capacity-four array to capacity eight requires transferring the existing four elements. That particular append can take linear time. When capacity grows by a fixed multiplicative factor, however, the total transfer work across many appends is linear in the number appended, giving amortized constant-time append. Growing capacity by exactly one slot each time does not provide the same bound and can repeatedly copy almost the entire sequence.

Choose an array for the operations you need

Fast indexed access does not imply fast lookup by value. Finding an unknown value in an unsorted array generally requires a linear scan, whereas a sorted random-access array permits binary search. Sequential traversal often benefits from locality, but actual timing also depends on element size, allocation, cache misses, and language checks. Compare arrays with lists or search trees using the complete workload: reads, appends, ordered middle insertions, and memory overhead. A complexity claim is useful only after the operation and representation are specified.

OperationConditionTime
Index accessIndex already knownO(1)
Value lookupUnsorted arrayO(n)
Middle insertionPreserve sequence orderO(n)
AppendMultiplicative capacity growthAmortized O(1)

Reading and practice are recorded separately in this browser, for each language.

Learn this in order

Build your CS foundations · STEP 9

Choose a learning path