The array is the most basic data structure there is — just a row of values sitting next to each other in memory. Almost everything else (stacks, hash tables, heaps) is built on top of it. To use arrays well you need two ideas: how they are laid out, and the Big-O cost model that tells you how fast each operation is.
Step through the animation on the right. First watch the index pointer jump straight to a[3] in one move (that is O(1)). Then watch it walk box by box to find a value it does not know the position of (that is O(n)).
The idea
An array is stored as one contiguous block of memory. Every box is the same size, so the computer can find box i with simple arithmetic: start_address + i × box_size. No searching — just one calculation.
That is why reading by index is instant. But the array does not know which index holds a given value. To find a value you have to look — and in the worst case you look at every box.
Walk through it
Press Play on the right, or step with Next / Back. Notice the two very different costs:
- Random access — the pointer lands on
a[3]in a single jump. It never touches the other boxes. One step, always. - Linear search — to find
23the pointer starts at index 0 and checks each box. Boxes it has already checked turn grey (visited); the box it is checking turns blue. It stops when it finds23at index 4.
The array had 6 boxes, and 23 was the 5th one, so the search checked 5 boxes. If the value were at the very end, it would check all 6. That growing-with-n cost is the whole point.
The code, line by line
a = [42, 17, 8, 99, 23, 4]
x = a[3] # random access: O(1)
def find(a, target):
for i in range(len(a)): # O(n) linear search
if a[i] == target:
return i
return -1- Line 2 —
a[3]is one memory lookup. It costs the same whether the array has 6 items or 6 million. That is O(1), constant time. - Lines 5–7 —
findwalks from index 0 upward. Each loop checks one box. If the target is missing it runs the loopntimes. That is O(n), linear time.
Complexity
| Case | Time | Notes |
|---|---|---|
| Access a[i] | O(1) (fast) | one address calculation |
| Search (unsorted) | O(n) (moderate) | may scan every box |
| Search (sorted) | O(log n) (fast) | binary search halves the range each step |
| Insert / delete (middle) | O(n) (moderate) | shift the rest of the boxes over |
O(n) (moderate)A quick tour of the Big-O classes you will meet most:
- O(1) — constant. The work does not grow with the input. Reading
a[i]is the classic example. - O(log n) — logarithmic. Each step throws away half the remaining work. Binary search on a sorted array does this — searching a million items takes about 20 steps.
- O(n) — linear. Work grows in step with the input. Linear search is O(n); so is reading every element once.
- O(n²) — quadratic. Work grows with the square of the input. A loop inside a loop (like comparing every pair) gets here fast — 1,000 items means about a million operations.
When to use / pitfalls
When an interviewer asks for the complexity of an array operation, anchor on index vs. value. Reaching a known position is O(1). Finding an unknown value is O(n) — unless the array is sorted, in which case you can binary-search in O(log n). Inserting or deleting in the middle is O(n) because every later element has to shift.
Big-O describes how cost grows, not the exact time. O(1) is not always faster than O(n) for a
tiny array — it ignores constant factors. Its real power is predicting what happens as n gets
large: an O(n²) algorithm that feels fine on 100 items can lock up on 100,000.
Practice
The array [42, 17, 8, 99, 23, 4] is unsorted. To find the value 4 (the last box) with linear search, how many boxes must we check?
1. Why is reading a[i] an O(1) operation?
2. Linear search for a value in an unsorted array is which complexity?
3. Which operation can run in O(log n)?
4. What does Big-O actually describe?