Quiz
Warm-up from lesson 1-2: reading `names[500]` from a Python list takes the same time whether the list has 1,000 or 1,000,000 items. Which Big-O family is that?
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).
Code exercise · python
Run this simulation of the address formula. Notice that finding slot 500 takes exactly the same one-line computation as finding slot 1: no loop anywhere.
Quiz
An array of 4-byte integers starts at address 2000. Where does item 6 live?
The hidden copy in a slice
One more consequence of contiguity. A slice like a[2:5] cannot simply point into the middle of a, because a list must own one contiguous block that it can grow, shrink, and reallocate (next lesson) without breaking anyone else. So Python allocates a new array and copies the k items in the range: a slice is O(k) time and memory, even though the syntax looks free.
Two things follow directly:
- editing a slice never changes the original — they are separate blocks
- slicing a big list inside a loop can quietly turn an O(n) pass into O(n²), the same trap you will meet with string
+in lesson 3-1
Code exercise · python
Run this. The slice is an independent copy: editing `piece` leaves `a` untouched. And the copy cost equals the slice's length — 50,000 items for the half slice, 10 for the tail slice — not the length of the whole list.
Problem
An array of 8-byte items starts at address 5000. An item lives at address 5080. What is its index?