FOUNDATIONS

ONE IDEA
BUILDS THE
NEXT

This is deliberately ordered. Everything tonight is built from the thing before it: arrays are memory with arithmetic, linked lists are pointers, hash tables are arrays plus a function, stacks and queues are either one, and merge sort is recursion wearing a costume.

If a block feels obvious, sit with it anyway. The gaps show up later as bugs, not as confusion.

EVERYTHING IS
AN ADDRESS

• The model. Memory is one enormous array of bytes. Every byte has a number. A variable is a human name for one of those numbers.
• A pointer is a value that happens to be an address. On a 64-bit machine it is eight bytes wide no matter what it points at.
• Two operators. &x takes the address. *p follows it, to read or to write.
• Why you care. Python and Java hide the syntax, not the idea. Assignment copies the reference, so two names can point at one object, and mutating through one is visible through the other.

MEMORY PLUS
ARITHMETIC

• Contiguous. One unbroken block. Element i lives at base + i × size, so indexing is arithmetic, not searching. O(1).
• Fast in practice. Neighbours arrive in the same cache line, so a linear scan over an array beats a linear scan over anything scattered.
• The price. Inserting or deleting in the middle shifts everything after it. O(n) per operation.
• Dynamic arrays. Full means allocate double, copy, continue. Any single append can be O(n), but the average over many appends is O(1).

THE EXACT
OPPOSITE TRADE

• Structure. Nodes scattered anywhere in memory. Each holds a value and the address of the next one. The list is the chain, not the block.
• Insert and delete at a position you already hold: O(1), just rewire two pointers. Nothing shifts.
• But finding that position is O(n), and there is no indexing at all. You walk.
• Costs you do not see. A pointer per node, and poor cache behaviour, because the next node can be anywhere.

AN ARRAY YOU
INDEX BY ANYTHING

• The trick. A hash function turns a key into an integer. Take it modulo the table size and you have an array index. Lookup becomes arithmetic again.
• Collisions are guaranteed. Infinite keys, finite buckets. Chaining hangs a list off each bucket; open addressing probes for the next free slot.
• Cost. O(1) on average. O(n) in the worst case, when everything lands in one bucket.
• Load factor. Past roughly 0.7 full, allocate a bigger table and rehash every key. That is why a single insert can occasionally be expensive.

SAME DATA,
DIFFERENT DOOR

• Stack. Last in, first out. One end for both push and pop. The call stack, undo, bracket matching, depth-first search.
• Queue. First in, first out. Add at the tail, remove from the head. Breadth-first search, scheduling, buffers.
• Both are O(1) for every operation. They are interfaces, not structures: build either over an array or a linked list.
• The array version of a queue wraps around, a ring buffer, so removing from the head does not shift anything.

THE HONEST
SLOW ONE

• The loop. Find the smallest value in the unsorted part. Swap it into the front of that part. Repeat on what is left.
• Comparisons. Always about n²/2, whether the input is sorted, reversed, or random. No best case.
• Swaps. At most n−1. That is its one genuine advantage: when writing is far more expensive than reading, selection sort writes the least.
• Properties. In place, O(1) extra space, and not stable in the classic swap form.

TRUST THE
SMALLER CALL

• Two parts. A base case that returns without recursing, and a recursive case that makes the input strictly smaller. Miss either and it never ends.
• The stack is real. Every call allocates a frame holding its parameters, locals, and where to return. Depth is memory, and running out of it is the stack overflow.
• Do not trace it. Assume the recursive call is already correct for the smaller input, then ask what you do with its answer. That leap is the skill.
• Cost. Write the recurrence. T(n) = 2T(n/2) + O(n) resolves to O(n log n), which is the next slide.

DIVIDE, THEN
DO THE WORK

• Divide. Split in half. Sort each half by the same procedure. A single element is already sorted, which is the base case.
• Conquer. Merging two sorted lists is linear: compare the two fronts, take the smaller, repeat.
• The cost. log n levels of splitting, O(n) of merging at each level. O(n log n) in every case, best and worst alike.
• Trade-off. Stable, predictable, and needs O(n) scratch space. That last part is why quicksort is often preferred in memory-tight code.

merge_sort(a):
    if len(a) <= 1: return a
    m = len(a) // 2
    L = merge_sort(a[:m])
    R = merge_sort(a[m:])
    return merge(L, R)