Array — static, dynamic; cache locality; amortized O(1) append
1. What is an array?
WHY contiguous? So we never store where the next element is — we compute it.
2. Static vs Dynamic arrays
The key trick: a dynamic array stores two numbers:
| Term | Meaning |
|---|---|
size |
how many elements you've actually put in |
capacity |
how many slots are allocated right now (capacity ≥ size) |
3. The append operation & amortized O(1)
WHAT happens on append(x):
- If
size < capacity: writexat indexsize, dosize++. → O(1) (cheap append). - If
size == capacity: allocate a new block of capacity , copy allsizeold elements, free old block, then write. → O(n) (expensive append).
Derivation: why doubling gives amortized O(1)
4. Cache locality — the hidden superpower
5. Complexity summary (the 80/20 table)
| Operation | Static array | Dynamic array |
|---|---|---|
Access a[i] |
O(1) | O(1) |
Update a[i]=x |
O(1) | O(1) |
| Append at end | n/a | O(1) amortized (O(n) worst) |
| Insert/delete at front/middle | O(n) (shift) | O(n) (shift) |
| Search (unsorted) | O(n) | O(n) |
| Space | O(n) | O(n), up to ~2× over-allocated |
Recall Feynman: explain to a 12-year-old
Imagine a row of identical lockers numbered 0,1,2… To open locker 5 you just walk straight to it — you don't open lockers 0–4 first. That's why arrays are instant to read. Now suppose the row is full and you want one more locker. You can't glue one onto the end (the wall's there). So you build a new row twice as long, carry all your stuff over, and keep going. Doing this doubling trick means you only move stuff occasionally, so on average adding a locker is still cheap. Bonus: because the lockers are in one straight line, when you grab from locker 5 your hands are already near 6,7,8 — the computer "grabs a handful at once." Scattered lockers (linked list) would make you run back and forth.
Flashcards
What single property of arrays gives O(1) access AND cache locality?
Derive the address formula for element i.
Why is dynamic-array append O(1) amortized not O(1) worst-case?
What two numbers does a dynamic array track and how do they relate?
Total copy cost of n appends with doubling growth?
Why does growing by a constant (+1) make append O(n) amortized?
What is a cache line and why do arrays exploit it?
For 64-byte lines and 4-byte ints, how many elements per fetch?
Cost of inserting at the front of an array?
Static vs dynamic array key difference?
Connections
- Linked List — opposite trade-off: O(1) splice but poor cache locality, O(n) access.
- Amortized Analysis — aggregate / accounting / potential methods generalize the doubling argument.
- Geometric Series — the bound underpinning O(1) append.
- CPU Cache and Memory Hierarchy — why contiguity beats equal Big-O structures.
- Hash Table — uses dynamic arrays (buckets) and the same doubling/rehash growth.
- Stack (Data Structure) — typically implemented on a dynamic array; push = amortized O(1) append.
- Big-O Notation — worst vs amortized vs average.
Concept Map
Hinglish (regional understanding)
Intuition Hinglish mein samjho
Dekho, array ka sabse bada raaz sirf ek hai: saara data memory me ek saath, lagataar (contiguous) rakha jaata hai, aur har element ka size same hota hai. Isi wajah se computer ko a[i] dhoondhne ke liye kahin search nahi karna padta — wo seedha formula laga deta hai: addr(i) = B + i·s, jahan B starting address aur s element ka size hai. Bas ek multiply aur ek add — isliye access O(1) hota hai, chahe array kitna bhi bada ho.
Ab dynamic array (jaise Python list, C++ vector, Java ArrayList) andar se ek static array hi hota hai, par usme do cheezein store hoti hain: size (kitne element daale) aur capacity (kitni jagah allocate hai). Jab size == capacity ho jaata hai aur tum naya element daalte ho, to ek badi block banani padti hai aur saara purana data copy karna padta hai — ye step O(n) hai. Par yahan trick hai: agar tum capacity ko har baar double karte ho (×2), to resize bahut kam baar hota hai. Pure n appends ka total copy kaam 1+2+4+… < 2n hota hai, yaani O(n) total, to per-append average O(1) amortized. Agar galti se tum sirf +1 karke badhao, to har baar resize hoga aur total kaam n²/2 ho jaayega — bahut slow. Isliye yaad rakho: hamesha multiply karo, kabhi sirf add mat karo.
Ek aur chhupa hua faayda: cache locality. CPU ek baar me 64-byte ka "cache line" uthata hai. Array contiguous hai, to jab tum a[5] padhte ho, a[6], a[7]… already cache me aa jaate hain — almost free. Linked list me nodes memory me bikhre hote hain, har next ek cache-miss — isliye same O(n) hone par bhi array practically 5–10x fast nikalta hai. Yahi reason hai ki real competitive programming aur system code me array/vector pehli pasand hota hai.