Data Structures & Algorithms, Animated

Direct addressing is the ideal case: A[k] is a single address computation. It is only practical when the universe U is small. If |U| = 10⁶ but you store 5 keys, you allocated a million slots for five entries — that is the O(|U|) space cost that hashing fixes.

A hash function must be deterministic and uniform. With load factor α = n/m, an unsuccessful search scans on average α nodes in the chain — O(1+α). If the hash collapses everything into one bucket, α becomes n and you are back to O(n).

Open addressing removes pointers, so the whole table is one contiguous array — excellent cache behaviour. The price is that the load factor α must stay below 1: as α → 1 the expected number of probes explodes to 1/(1−α). Deletion requires tombstones (a DELETED marker) rather than emptying the slot.

In the two-children case the successor is the minimum of the right subtree — the smallest key larger than the deleted one. Transplanting it preserves the in-order sequence. The cost is the height h: O(log n) when balanced, O(n) when the tree degenerates into a chain.

A rotation is a pure pointer shuffle — constant time, no data movement. That is why red-black trees guarantee O(log n) inserts and deletes: at most O(log n) recolourings plus at most 3 rotations, each O(1).

The naïve recurrence solves the same subproblem r[j] exponentially many times. DP stores each answer once: the inner loop over i costs j, summed over j gives Θ(n²). The s[j] array records the optimal first cut, letting us reconstruct the pieces in O(n).

m[i][j] = minimum cost to multiply A_i…A_j. There are O(n²) subproblems, each trying O(n) split points → Θ(n³). The s[i][j] table records the optimal split so the parenthesization can be rebuilt in O(n).

If x_i = y_j the LCS grows by one; otherwise it is the max of dropping a character from either string. Filling the table costs Θ(mn); the traceback is O(m+n). Only two rows are needed for the length — full storage is needed to reconstruct the subsequence.

e[i][j] is the expected cost of an optimal BST on keys i…j. Adding the weight w(i,j) accounts for every key on the path being one level deeper. The root[i][j] table records the chosen root, reconstructing the tree in O(n).

The greedy choice — take the activity that finishes first — is safe because it leaves the largest possible remaining time for the rest. This is the exchange argument: any optimal solution can be swapped to include the earliest-finishing activity without getting worse. The O(n log n) comes entirely from the sort; the scan itself is linear.

Huffman's algorithm is greedy but provably optimal: the two least-frequent symbols can always be placed as siblings at maximum depth. Merging them and recursing gives a prefix-free code — no codeword is a prefix of another — so decoding needs no separators. Each merge costs O(log n) with a heap → O(n log n).

Bélády is the optimal offline paging algorithm. The greedy exchange argument proves that evicting the block used farthest in the future never hurts. Real systems cannot see the future, so they approximate it with LRU (least-recently used) — typically within a constant factor of optimal on real traces.

With doubling, the total work to do n insertions is 1 + 1 + 2 + 1 + 4 + … = 2n − 1 = O(n), so the amortized cost per insert is O(1). The potential function Φ(T) = 2·num[T] − size[T] captures the “saved-up” work: every cheap insert raises Φ by 2, every expensive resize drops it — the amortized cost is exactly 3. Growing by a constant increment instead of doubling would give Θ(n) amortized.