An array is a row of equal-size boxes placed side by side in memory , so the computer can jump straight to box number i
Before you can derive anything in the parent note , you need to fully own every word and symbol it throws at you. This page builds each one from nothing. Read top to bottom — each block earns the next.
Definition Memory & addressComputer memory is one gigantic single-file line of numbered slots, each slot holding one byte (one small chunk of data). The address of a slot is just its position number in that line — like a house number on an infinitely long street.
Picture memory as a ruler laid flat: position 0, 1, 2, 3, … going right forever. When we say a piece of data "lives at address 1000", we mean it sits at the 1000th tick on that ruler.
B first slot of our array — where the whole block begins . We call it B B ase). Everything in the array is measured relative to B
Why the topic needs it: the parent's headline formula addr ( i ) = B + i ⋅ s B i
s size , written s int is often s = 4 double is s = 8 every element has the same s
Picture each array element as an identical box of width s
Intuition Why "same type / same size" is the whole gameIf boxes had different widths, you couldn't predict where box 5 begins without walking past boxes 0–4 to add up their widths. Equal width is exactly what lets you multiply instead of walk . That single constraint is the seed of O(1) access.
Why the topic needs it: s i ⋅ s L / s
i index is which box you mean, counted starting at 0 . Box 0 is the first, box 1 the second, … box n − 1 i
Common mistake "The first element is number 1."Why it feels right: humans count 1, 2, 3.
The fix: arrays count offsets from the base . Box 0 sits at B + 0 ⋅ s = B is index 0, and the formula stays clean. If you started at 1, you'd need B + ( i − 1 ) s
Why the topic needs it: the range 0 … n − 1 arr[5], and in every trace.
n n how many elements are in the array right now. The valid indices are 0 n − 1 n
Why the topic needs it: "O(1) regardless of n " is the punchline of array access. And n
Now that B s i
Intuition Why this tool: multiply, not a loopWe could walk box by box (a loop, O(n) steps). But because every step is the identical size s one multiplication i ⋅ s i
Two counts that look alike but mean different things — the parent leans on both.
Definition size and capacity
sizefilled with your data.capacitypainted/reserved in memory, ready to receive data.
Always capacity ≥ size
Picture a row of 8 reserved boxes where only the first 3 hold values: capacity = 8 size = 3
Common mistake "size and capacity are the same thing."Why it feels right: in a full array they're equal.
The fix: the gap between them is precisely what makes a cheap append possible — a spare box to write into without asking memory for more. When the gap hits zero (size = capacity
g g g = 2 g = 1.5 g = 2
Why the topic needs it: whether append is O(1) amortized or O(n) amortized depends entirely on g multiplicative (g > 1 additive (+1, a constant). This one choice is the hinge of Section 3.
Definition Big-O — the growth-shape symbolO ( ⋅ ) how the work grows as n , ignoring constant factors.
O ( 1 ) flat — same cost no matter how big n O ( n ) straight line — double the data, double the work.O ( n 2 ) steep curve — double the data, quadruple the work.
Intuition Why we ignore constantsA step that always takes "3 operations" and one that takes "50 operations" are both O ( 1 ) shape of the growth, because for large n Big-O Notation for the full story.
Why the topic needs it: every claim in the parent is a Big-O claim — access O ( 1 ) O ( n ) O ( n 2 )
Definition Amortized costThe average cost per operation across a long run , when a few operations are expensive but most are cheap. Total work over n n
Most appends are cheap O ( 1 ) O ( n ) Amortized Analysis .
Why the topic needs it: "O ( 1 )
Definition Geometric seriesA sum where each term is a fixed multiple of the previous one. Doubling gives 1 + 2 + 4 + 8 + ⋯ + 2 k less than twice the last term .
Why the topic needs it: this is the engine of the amortized proof — total copy work < 2 n Geometric Series .
L line of L L = 64
Picture the memory ruler chopped into fixed 64-tick chunks; touching any tick loads its entire chunk.
Why the topic needs it: L / s very ones you'll read next . Background: CPU Cache and Memory Hierarchy .
Each box on the left is defined on this page; together they feed the parent topic on the right.
You are ready for the parent note when you can answer each without peeking:
What does the base address B The memory address of the array's first element (box 0).
What is the element size s Bytes each element occupies; constant s
Starting index of an array, and why? 0 — so box i B + i ⋅ s
What is n The number of elements currently stored; valid indices 0 … n − 1
State the address formula and read it in words. addr ( i ) = B + i ⋅ s B i s
Difference between size and capacity? size = boxes filled; capacity = boxes reserved; capacity ≥
What is the growth factor g The multiplier for a new block on resize; it must be > 1
What do O ( 1 ) O ( n ) O ( n 2 ) Flat, straight line, steep upward curve of work versus n
Define amortized cost in one sentence. Total cost over many operations divided by the number of operations, spreading rare expensive steps over cheap ones.
Value of 1 + 2 + 4 + ⋯ + 2 k 2 k + 1 − 1 2 ⋅ 2 k
What is a cache line L A ~64-byte chunk loaded at once; L / s
"B, s, i pick the box; size vs cap picks the fight; g
