Base CS from zero
Indexing and offsets
You now know an array is one contiguous block of equal-size cells. But when you write
scores[3], how does the program find element 3? It does not search. It does not walk
from the start counting cells one by one. It computes the exact address of element 3 in a
single arithmetic step and reads directly from there.
That single step is the whole reason arrays are everywhere in programming. It explains why
arr[3] and arr[3000] take exactly the same amount of time, and it explains a fact that
puzzles every beginner: why the first element is arr[0] and not arr[1].
This lesson opens up that arithmetic. After it, the bracket syntax will no longer be magic — it will be a formula you can compute by hand.
After this lesson you can define the index and the offset of an array element, state the formula that converts an index into a memory address, explain why element 0 is the first element, and explain why reaching any element takes the same constant amount of time.
The base address. From the previous lesson: an array is one contiguous block, and the array name refers to where that block begins. That starting address has a name: the base address of the array. It is the byte address of the array’s very first cell.
Every other element’s address will be measured relative to the base address. The base address is the fixed anchor point; everything else is computed from it. The program knows the base address as soon as the array exists — finding it costs nothing.
The index and the offset. The index of an element is its position counted from
the start of the array: the first element has index 0, the next has index 1, then 2, and
so on. The index is the number you write inside the brackets: arr[2] means “the element
at index 2”.
The offset of an element is how many bytes past the base address that element’s cell begins. Index counts elements; offset counts bytes. They are related by the element size:
offset = index x element_sizeIf each element is 4 bytes, then index 0 has offset 0, index 1 has offset 4, index 2 has
offset 8, and so on. The offset of index i is just i element-sizes worth of bytes.
The address formula. An element’s actual memory address is the base address plus its offset. Putting the two pieces together:
address of element i = base_address + (i x element_size)This one line is how arr[i] works. To read arr[i], the program: takes the base address
(already known), multiplies the index i by the element size, adds that offset to the base
address, and reads the cell at the resulting address. One multiply, one add, one read.
Notice what is not in the formula: the array’s length, and any of the other elements.
The address of element i depends only on the base address, the index, and the element
size. It does not matter whether the array has 10 elements or 10 million.
Why the first element is index 0. Now the “off-by-one” mystery dissolves. The index is not a count of “which element” in everyday terms — it is the offset measured in elements from the start of the block.
The first element sits exactly at the base address. It is zero elements past the start.
Its offset is 0 x element_size = 0. So its address is base_address + 0 = base_address.
The index that produces an offset of zero is 0 — therefore the first element is
arr[0]. Index 0 is not a quirk of syntax; it is the only index whose offset is zero, and
the first element is the only element with a zero offset. The numbering is forced by the
arithmetic.
Constant-time access. Because the address of any element is found by the same fixed
work — one multiply, one add, one read — reaching arr[0] costs exactly as much as
reaching arr[9999]. The amount of work does not grow with the index, and it does not grow
with the size of the array.
Work that takes the same fixed amount regardless of the input size is called constant time. Array indexing is the classic example. This is the single most important property of arrays: any element, no matter where it sits, is one arithmetic step away.
Why this works
Why is this only possible because the array is contiguous and equal-size? The formula
base + i x element_size works only if the cells are uniform and gapless. If elements
had different sizes, you could not multiply the index by a single element size — you would
have to add up the sizes of all the earlier elements one by one, which is no longer
constant time. If there were gaps, the multiplication would land on the wrong address. The
two array properties from the previous lesson — equal-size and contiguous — are exactly
what make the constant-time formula valid.
Computing the address of scores[3].
The array scores has base address 1000. Each element is a number taking 4 bytes. We want
the address of scores[3].
Step 1 — Identify the pieces.
- base_address = 1000
- index
i= 3 - element_size = 4 bytes
Step 2 — Compute the offset. The offset is the index times the element size: offset = 3 × 4 = 12 bytes. Element 3 begins 12 bytes past the start of the block.
Step 3 — Compute the address. The address is the base plus the offset:
address = 1000 + 12 = 1012. The cell for scores[3] starts at address 1012.
Step 4 — Read. The program reads the value stored at address 1012. Done.
Now check scores[0]: offset = 0 × 4 = 0, address = 1000 + 0 = 1000 — exactly the base
address. The first element sits right at the start, which is why its index is 0. And check
scores[4]: offset = 4 × 4 = 16, address = 1016. Every one of these took the same one
multiply and one add — that is constant-time access.
Common mistake
A common mistake is to think the program “walks” to arr[i] by stepping through elements
0, 1, 2, … up to i. It does not. Walking would make arr[5000] far slower than
arr[5]. The program jumps straight to the address using the formula. The index is not a
number of steps to take — it is an input to a one-shot address calculation.
An array has base address 1000 and element size 4 bytes. Using address = base + index x element_size, what is the address of element 2?
An array has base address 500 and element size 8 bytes. What is the address of element 0 (the first element)?
An array has element size 4 bytes. The offset of element i is i x element_size. What is the offset (in bytes) of element 5?
An array has base address 2000 and element size 4 bytes. What is the address of element 7?
Reaching any element of an array takes one multiply, one add, and one read — the same fixed work regardless of the index. Reaching element 9000 of a large array, compared to reaching element 3, takes: type 1 if the same amount of work, 0 if much more work.
Why can a program reach arr[i] in constant time — the same speed for any index?
The base address of an array is the byte address of its first cell — the fixed anchor
the array name refers to. An element’s index is its position counted from 0; its
offset is how many bytes past the base address its cell begins, equal to
index × element_size. The address of element i is therefore
base_address + (i × element_size) — one multiply, one add. Element 0 is the first element
because its offset is 0 × element_size = 0, placing it exactly at the base address; no
other index has a zero offset. Because the formula uses the same fixed work for any index,
and never touches the array’s length or the other elements, reaching any element takes
constant time. This constant-time address arithmetic is only valid because the array
is contiguous and made of equal-size cells.