Recall from lesson 1-2 that reading names[500] takes the same time whether the list holds 1,000 items or 1,000,000. That is constant time, O(1).
Nothing about the list's size enters into the work, which is what constant time means.
This lesson explains the memory trick that makes it possible. The position of slot 500 can be computed rather than searched for, and computing it takes the same two operations regardless of how many slots exist.
One long row of boxes
Your computer's memory (RAM) is one giant row of numbered byte-sized cells. The number of a cell is its address.
An array is the simplest possible structure: n equal-sized items stored in one contiguous block of memory, side by side with no gaps. If the array starts at address 5000 and each item takes 8 bytes, then:
- item 0 lives at 5000
- item 1 lives at 5008
- item i lives at 5000 + i × 8
That formula is the whole secret. To read item 500 the computer does one multiply and one add, then jumps straight to that address. No scanning, no counting up from the start. That is why indexing is O(1).
The address formula in action
Simulating the arithmetic makes the constant-time claim concrete.
base = 5000 size = 8 for i in [0, 1, 2, 500]: print(f"nums[{i}] -> address {base + i * size}")
Output
nums[0] -> address 5000 nums[1] -> address 5008 nums[2] -> address 5016 nums[500] -> address 9000
Here base is the pretend starting address of the array and size is the bytes per slot.
Finding slot 500 took exactly the same one-line computation as finding slot 1. There is no loop anywhere in this code, and that absence is the O(1). Adding a million more slots would not add a single operation.
The requirement hiding behind the formula is uniformity. Every slot has to be the same size, or i * size would not land anywhere meaningful, which is why arrays hold items of one type in lower-level languages.
Item 6 of a 4-byte integer array starting at address 2000 lives at address 2024.
The formula is address = base + i × size, so 2000 + 6 × 4 = 2024.
This is the arithmetic the computer performs for every index read, one multiply and one add. Because it is arithmetic rather than search, the position is never looked for, which is the entire reason indexing does not slow down as the array grows.
The hidden copy in a slice
Contiguity has another consequence, and this one costs money.
A slice like a[2:5] cannot simply point into the middle of a. A list has to own one contiguous block that it can grow, shrink, and reallocate, which the next lesson covers, without breaking anything else that refers to it. So Python allocates a new array and copies the k items in the range, making a slice O(k) in both time and memory even though the syntax looks free.
Two things follow directly.
- Editing a slice never changes the original, because they are separate blocks of memory.
- Slicing a big list inside a loop can quietly turn an O(n) pass into O(n²), the same trap that string concatenation sets in lesson 3-1.
That second point is the practical one. A loop that runs n times and slices half the list on each pass does n × n⁄2 copying, and nothing in the code looks like a nested loop.
Proving the copy is real
Two things to check: whether a slice shares memory with its source, and what the copy actually costs.
a = list(range(10)) piece = a[2:5] print("piece:", piece) piece[0] = 99 print("piece after edit:", piece) print("a[2] unchanged:", a[2]) big = list(range(100000)) left_half = big[:50000] last_ten = big[-10:] print("items copied by big[:50000]:", len(left_half)) print("items copied by big[-10:]:", len(last_ten))
Output
piece: [2, 3, 4] piece after edit: [99, 3, 4] a[2] unchanged: 2 items copied by big[:50000]: 50000 items copied by big[-10:]: 10
Setting piece[0] = 99 left a[2] at 2, so the slice is an independent block rather than a window onto the original.
The second half measures the cost. The half slice copied 50,000 items and the tail slice copied 10, from the same 100,000-item list. The price depends on the slice's length, not the list's, which is exactly what O(k) says.
That is also the practical rule for avoiding the trap. A small slice of a huge list is cheap, and a large slice is not, so the question to ask is how much you are taking rather than how big the source is.
The item at address 5080 in an 8-byte array based at 5000 sits at index 10.
The formula runs backward as easily as forward. Rearranging address = base + i × size gives i = (address − base) ÷ size, so (5080 − 5000) ÷ 8 = 80 ÷ 8 = 10.
The fact that the relationship is invertible is worth noticing, because it means an address and an index carry the same information. That is what allows a program to hand around a pointer into an array and have the receiver work out which element it refers to.