Overview

O is an upper bound (guarantees no worse than); Omega is a lower bound (guarantees no better than); Theta is a tight bound (both hold simultaneously, so it pins the growth rate exactly). Calling a genuinely Theta(n) algorithm "O(n^2)" is technically true but throws away the tighter, more useful claim -- it undersells what you actually know about the algorithm's growth (Examples 1, 2, 8, 15, 74, 78).

Aggregate (total cost across a whole sequence, divided by the number of operations), accounting (a credit ledger per operation that must never go negative), and potential (a function of the data structure's state whose change, plus the actual cost, stays bounded). All three prove the same claim -- "amortized O(1)" -- through different lenses (Examples 25, 26, 33, 77).

A recursive call's own complexity depends on the complexity of the smaller subproblems it calls, which is exactly what a recurrence like T(n) = 2T(n/2) + n encodes -- the "how many times does this call itself, on what size" structure has to be turned into an equation and unrolled (or solved via the Master theorem) before a closed-form bound like O(n log n) falls out (Examples 3, 4).

For any recurrence of the shape T(n) = a*T(n/b) + f(n), the Master theorem mechanically compares f(n) against n^(log_b a) and picks one of three cases -- it replaces a fresh, case-by-case unrolling derivation for every new divide-and-conquer algorithm with a single, reusable comparison (Example 4).

A Fenwick or segment tree (extra O(n) space buys O(log n) range queries instead of an O(n) rescan), memoization (a cache buys avoiding recomputation), and a precomputed lookup table generally -- recognizing the tradeoff explicitly is what makes the decision to spend memory deliberate rather than accidental (Examples 62, 78, 79).

After the subproblems are solved independently and recursively, combine merges their results back into a solution for the whole problem -- in merge sort, that's the linear-time merge of two sorted halves, and in closest-pair, it's the strip check across the dividing line. The split and recurse steps are often mechanical; the combine step is usually where the algorithm's actual cleverness (and its complexity) concentrates (Examples 5, 29).

A property checked only at the end is a weaker, later-arriving signal -- if it fails, you know something went wrong somewhere in the whole run, but not where. Checking continuously, right after each append, catches a violation at the exact step that introduced it, which is strictly more useful for debugging (Examples 5, 6).

The O(n log n) reputation is an AVERAGE-case bound -- it depends on partitioning splitting the array roughly in half. A fixed-pivot strategy (like "always the last element") degrades to O(n^2) on already-sorted input, because every partition splits off just one element, mirroring the worst case exactly (Examples 7, 8, 27, 28, 74).

It guarantees the root is always the minimum (or maximum) of the whole heap, and that every parent-child pair obeys the ordering relation. It does NOT guarantee the heap is a fully sorted structure at any level below the root -- siblings and cousins can be in any relative order, which is exactly the relaxation that makes O(log n) push/pop possible instead of O(n log n) (Examples 9, 10).

The n log n bound applies specifically to sorts that only compare pairs of elements; counting and radix sort never compare elements at all -- they exploit a structural assumption (a small known key range, or fixed-width digits) to place elements directly. What they give up is generality: they only work when that structural assumption genuinely holds (Examples 11, 12).

Radix sort's correctness DEPENDS on every per-digit pass being stable -- an unstable earlier pass would scramble the relative order that a later, more-significant digit's pass relies on to be correct. Stability isn't a nice-to-have property here; it's a precondition the algorithm's correctness proof assumes (Example 13).

A plain BST's height depends entirely on insertion order -- inserting keys in sorted order produces a degenerate, linked-list-shaped tree with O(n) height, so O(log n) search only holds for insertion orders that happen to keep the tree roughly balanced. AVL and red-black trees make O(log n) height structural, via rotations (and, for red-black, color invariants), regardless of insertion order (Examples 14, 15, 68, 69).

"Which strings share this prefix" -- a hash table only supports exact-key lookup; walking a trie down to a prefix's node and counting the words beneath it answers a prefix query in O(prefix-length), which is exactly what powers autocomplete and spell-checking (Examples 16, 17).

A plain array gives O(1) point-update but O(n) prefix-sum query; a precomputed prefix-sum array flips that to O(1) query but O(n) update. A Fenwick tree gets BOTH operations to O(log n), at the cost of O(n) extra space and code that indexes by the lowest set bit rather than the position directly (Examples 30, 67).

A segment tree generalizes to any associative aggregate (min, max, GCD, sum -- not just sum) and supports efficient RANGE updates via lazy propagation; a Fenwick tree is specialized to prefix sums and point updates. The cost is roughly 4x the memory and meaningfully more code to get right (Examples 31, 32, 67).

Union-by-rank keeps the resulting tree shallow by always attaching the smaller tree under the larger tree's root (rather than risking a long chain); path compression flattens every node visited during a find() directly to the root, so future queries on those same nodes are O(1). Together they turn a structure that can degrade toward a linked list into one with (amortized) near-constant-time operations (Examples 22, 33, 34, 42).

A plain boolean can't tell "this node is my ancestor on the current recursion path" (GRAY) apart from "this node was already fully explored on some unrelated branch" (BLACK) -- and that distinction is exactly what separates a genuine back-edge (a cycle) from a harmless cross-edge to an already-finished subtree (Examples 18-21, 36, 37, 66).

Kahn's algorithm repeatedly removes in-degree-zero nodes -- if the output order ends up shorter than the node count, a cycle exists (some nodes never reached in-degree zero). The DFS-based approach reverses DFS finish order -- a back-edge encountered during the DFS (via GRAY-node coloring) signals a cycle directly (Examples 35, 36, 37, 65, 66, 80).

Dijkstra assumes edge weights are non-negative, which guarantees that once a node is popped from the heap with the smallest known distance, no LATER relaxation could ever produce something smaller -- so it's safe to finalize that node immediately. A negative edge breaks that guarantee: a cheaper path could still arrive later through an edge that subtracts from the running total (Examples 38, 39, 43, 63, 64, 80).

O(V*E) instead of O((V+E) log V) -- Bellman-Ford relaxes every edge V-1 times over, never finalizing a node early, which is exactly what makes it correct in the presence of negative edges but also what makes it structurally slower on the common case of non-negative weights (Examples 40, 41, 63).

Kruskal's is greedy on EDGES (cheapest edge first, skipping any that would form a cycle, checked via union-find); Prim's is greedy on NODES (cheapest edge that extends the current tree, via a heap). That two structurally unrelated strategies always converge on the same minimum total weight is a strong, independent correctness signal for both (Examples 42, 43).

The same locally-optimal heuristic can be provably optimal for one problem (interval scheduling by earliest finish time) and provably WRONG for a closely related one (0/1 knapsack, where fractional knapsack's greedy-by-ratio strategy doesn't transfer) -- the greedy-choice property is a fact about a SPECIFIC problem's structure, not a general guarantee (Examples 44, 45, 58, 79).

No -- DP is the PRINCIPLE of never solving the same overlapping subproblem twice, implementable either top-down (memoization: recurse normally, but cache results) or bottom-up (tabulation: fill a table from the smallest subproblem upward). Which implementation fits best depends on the problem's dependency structure, not on DP itself dictating one form (Examples 45-48, 58, 60, 79).

A reconstruction step -- the filled table stores enough information (which choice led to each cell's optimal value) to walk backward from the final cell and recover an actual optimal SOLUTION, not just its numeric value. That's what a real diff tool or a version-control merge needs: not just "how different are these," but the actual edit sequence (Examples 49-51, 59, 61, 62, 65, 80).

Checking constraints immediately after EACH placement (not only at the end) lets a hopeless branch be abandoned the moment it becomes invalid, before any further, wasted recursion explores it -- that early pruning is the entire difference between a fast, practical backtracking search and a brute-force enumeration that happens to also check validity (Examples 53-57).

Sortedness or monotonicity -- two pointers converging from opposite ends only works because moving one pointer inward has a PREDICTABLE effect on the running sum/condition (sorted data). A sliding window's incremental update similarly relies on the window's boundary conditions being monotonic. Without that structure, there's no way to know which pointer to move without still checking every pair (Examples 23, 24, 70-72).

Monotonicity of a predicate over a VALUE space -- if some value V satisfies a yes/no predicate, every value on one side of V also satisfies it (and every value on the other side doesn't). That's a much broader condition than "sorted array": it applies to "minimum capacity that lets you ship in D days" just as well as to array indices, because the predicate "can you ship in D days with capacity C" is monotonic in C (Examples 52, 60, 73).

Between "guaranteed optimal, but only feasible for small inputs" (brute force) and "fast at any realistic scale, but with no optimality guarantee" (a heuristic) -- there is, as far as anyone has proven, no polynomial-time algorithm that gives both. Recognizing which category a NEW problem falls into (often via a reduction from a known NP-hard problem) is itself the practical skill, separate from actually solving the problem (Examples 75, 76).

This is a non-comparison-sort opportunity (co-10) -- the key range is small and known (0-999), which is exactly the structural assumption counting sort exploits: O(n+k) with k=1000, no comparisons at all, beating the n log n floor that only bounds comparison sorts (Examples 11, 12).

This calls for a trie (co-13) -- a hash table can't efficiently answer a prefix query at all, while walking a trie down to the matching prefix's node is O(prefix-length), independent of how many other prefixes are stored (Examples 16, 17).

A Fenwick tree (co-14) -- both point-update (correcting one reading) and prefix-sum query (used to compute any range sum by subtraction) land in O(log n), the efficient middle ground between an O(1)-update-but-O(n)-query plain array and an O(1)-query-but-O(n)-update precomputed prefix array (Examples 30, 67).

A segment tree with lazy propagation (co-15) -- a Fenwick tree is specialized to prefix sums; a segment tree generalizes to any associative aggregate (min included) and supports efficient RANGE updates via lazy propagation, at the cost of more code and memory (Examples 31, 32, 67).

Topological sort with cycle detection (co-18) -- Kahn's algorithm (or the DFS-based variant) produces the valid order directly, and a shorter-than-expected output (Kahn's) or a detected back-edge (DFS) is exactly the cycle signal (Examples 35-37, 65, 66, 80).

Dijkstra's algorithm with a heap (co-19) -- since all weights are non-negative, Dijkstra's greedy finalize-on-pop strategy is valid and its O((V+E) log V) beats Bellman-Ford's O(V*E), which is only needed when negative weights are possible (Examples 38, 39, 43, 63).

Bellman-Ford (co-20) -- it's the only one of the two shortest-path algorithms in this topic that tolerates negative edges at all, and its extra relaxation round is precisely the mechanism for detecting a negative cycle (which, in this domain, would represent unbounded arbitrage profit) (Examples 40, 41).

A minimum spanning tree, via Kruskal's or Prim's (co-21) -- this is not a shortest-path problem (which optimizes cost between two specific nodes); it's a spanning problem (minimize the TOTAL cost of a tree connecting every node), which is exactly what MST algorithms solve, and either algorithm gives the same optimal total (Examples 42, 43).

The greedy paradigm applies directly here (co-22), because the problem statement includes the proof that the greedy-choice property genuinely holds -- this is interval scheduling, one of the few problems in this topic where greedy is proven optimal, not just heuristically reasonable (Example 44).

This is 0/1 knapsack, and it needs 2D dynamic programming instead of greedy (co-24, co-22) -- greedy's optimality was specific to the FRACTIONAL version (where you can take a partial item); the 0/1 constraint (each item is all-or-nothing) breaks the greedy-choice property, and only DP, exploring every combination via the table, finds the true optimum (Example 58).

Backtracking (co-25) -- the defining characteristic (commit to a choice, recurse, immediately abandon any branch that violates a constraint) is exactly this shape; N-Queens, Sudoku, and constrained placement puzzles all reduce to backtracking with problem-specific validity checks (Examples 53, 57).

Settle for a heuristic (co-28) -- once a problem is recognized as NP-hard (or is suspected to be, pending a reduction proof), the practical engineering choice is between guaranteed-optimal-but- infeasible-at-scale and fast-but-unguaranteed; a nearest-neighbor-style heuristic (as used for TSP) trades the optimality guarantee for tractability (Examples 75, 76).

Root cause: the partition function moved every element <= pivot into the left region but never performed the final swap that places the pivot itself between the <= pivot and > pivot regions -- without that swap, the pivot stays wherever it started, and the "partition point" returned to the caller does not reflect any real separation.

Run: python3 kata.py

Output:

[2, 3, 4, 5, 8]
True

Root cause: sift-down only ever considered the left child as the swap candidate, so whenever the RIGHT child was the smaller of the two, the heap property silently failed to hold at that node -- is_min_heap() catches this because it checks every node, not just the root, which still happens to end up correct by coincidence on many inputs.

Run: python3 kata.py

Output:

[0, 1, 3, 2, 8, 5, 9]
True

Root cause: selection sort's long-range swap can move an element past another element with an equal key without either of them ever being compared to each other directly, silently reordering them -- sorted() is guaranteed stable by the language, which is exactly why it's the correct default choice whenever equal-key order matters.

Run: python3 kata.py

Output:

[(85, 'bob'), (85, 'dave'), (90, 'alice'), (90, 'carol')]
True

Root cause: overwriting parent[a] directly discards whatever a was already pointing to -- when a already had a parent from an earlier union(), that earlier link is silently replaced rather than merged with. Resolving both a and b to their CURRENT roots first, then attaching root to root, is what makes repeated unions compose correctly.

Run: python3 kata.py

Output:

True
True

Root cause: Kahn's algorithm can only place a node once its in-degree reaches zero -- on a pure cycle, NO node ever reaches in-degree zero, so the queue starts empty and the loop never runs at all, silently returning an empty list. Checking len(order) == len(graph) after the loop is the mechanical way to detect this and fail loudly instead of returning a silently-wrong partial order.

Run: python3 kata.py

Output:

graph has a cycle -- only 0/3 nodes reached in-degree 0

Root cause: Dijkstra's visited set finalizes B the moment it is first popped (via the cheap DIRECT edge, distance 1), and B is never reprocessed even after A's negative edge later discovers a better distance to B -- so the improvement never propagates on to C. Bellman-Ford has no notion of "finalized"; it relaxes every edge repeatedly, so the negative-edge improvement is guaranteed to propagate correctly within V-1 rounds.

Run: python3 kata.py

Output:

-5
True

Root cause: "always take the largest coin that fits" has no proof of optimality for an arbitrary coin set -- it happens to be optimal for canonical coin systems (like US currency) but fails on {1, 3, 4}, where taking 4 first forces two more 1-coins. DP explores every coin choice at every amount, so it finds the genuine minimum regardless of whether the coin set is canonical.

Run: python3 kata.py

Output:

[3, 3]
2
True

Root cause: fib(n - 1) internally recomputes fib(n - 2) all over again, and that duplication compounds at every level of the recursion tree, producing exponentially many redundant calls. Caching each n's result the first time it's computed means every subsequent request for that same n returns instantly instead of re-recursing -- the exact "never solve the same subproblem twice" principle DP is built on.

Run: python3 kata.py

Output:

75025
49
True

Root cause: the search commits a column to cols on the way down but never releases it on the way back up -- after the very first full-depth attempt returns (successful or not), every column used along that attempt remains permanently "used," so no later sibling branch can ever place a queen in an already-visited column again. The missing cols.remove(col) / placed.pop() pair IS the "backtrack" in backtracking -- without it, this is just a single depth-first probe, not a search.

Run: python3 kata.py

Output:

2
True

Root cause: detecting a duplicate is not the same as RESPONDING to it -- the buggy version notices s[right] in seen but takes no action, so left never advances and the window's length keeps growing across every repeat, over-counting the whole string. The fix tracks each character's most recent INDEX (not just membership) and jumps left directly past that index the moment a repeat within the current window is found, which is what makes the window's length always reflect a genuinely repeat-free run.

Run: python3 kata.py

Output:

3
True

Because almost every optimization technique in this topic IS a space-time tradeoff wearing a different name -- a Fenwick or segment tree spends O(n) extra memory to turn an O(n) scan into an O(log n) query; memoization spends a cache to avoid recomputation; a space-rolled DP table deliberately gives that memory back once it's no longer needed. Recognizing co-05 explicitly is what turns "this happens to be faster" into "I am spending X memory to buy Y time, and here's why that's worth it" -- the abstraction-and-its-cost idea made concrete and measurable.

Greedy's optimality is a proven property of a SPECIFIC problem's structure (the greedy-choice property), not a general fact about "greedy algorithms." Fractional knapsack allows taking a partial item, which is exactly the flexibility the greedy-by-ratio proof depends on; the 0/1 constraint removes that flexibility, and with it, the proof -- the two problems only look similar at the level of "items, weights, values," not at the level of the structural property that actually makes greedy work.

Because the unconditional claim is false -- Dijkstra's greedy strategy specifically depends on the guarantee that once a node is popped with its currently-smallest distance, nothing later could ever produce something smaller, and that guarantee only holds when every edge weight is non-negative. Stating the assumption explicitly is what turns "use Dijkstra" from a habit into an engineering decision that gets re-examined the moment a negative edge shows up (which is exactly why Bellman-Ford exists as a fallback).

A plain BST's O(log n) bound is conditional -- it depends on insertion order happening to keep the tree balanced, and degrades to O(n) on sorted input. An AVL tree's rotations make O(log n) height a structural INVARIANT, true regardless of insertion order -- the difference isn't a performance tweak, it's a difference between a probabilistic hope and a proven guarantee, which is a difference in what you're actually allowed to claim about worst-case behavior.

Because amortized analysis is a WORST-CASE guarantee over any possible sequence of operations, not an empirical average over some observed runs -- a doubling dynamic array's append IS worst-case O(n) on the exact operation that triggers a resize, and the aggregate/accounting/potential methods are what prove the AVERAGE cost across any sequence is still O(1), regardless of which specific sequence an adversary picks. An empirical average over sample runs proves nothing about a sequence you haven't tried yet.

For a P problem, "solved" means an exact, polynomial-time algorithm exists and you should find it. For an NP-hard problem, no such algorithm is known to exist (and is widely believed not to), so "solved" has to mean something else: either an exact solution that's only feasible at small scale (brute force), or a fast heuristic with no optimality guarantee. The choice between those two is itself the practical skill -- treating an NP-hard problem as if it should have a clean polynomial solution wastes effort looking for something that (very likely) isn't there.

A segment tree's generality (supporting any associative aggregate and efficient range updates via lazy propagation) requires storing an explicit aggregate value at EVERY internal node of a full binary tree over the array, plus lazy-propagation bookkeeping at each node -- a Fenwick tree exploits the specific structure of prefix sums (via the lowest-set-bit indexing trick) to avoid storing that much redundant state. The extra memory buys generality: co-05's tradeoff made explicit, paying more space for a structure that solves a strictly larger class of problems.

"Exponential" describes an asymptotic upper bound, not the actual number of nodes visited on a specific input -- pruning a branch the moment it violates a constraint means that branch's entire remaining subtree, however large, is never explored at all. On real inputs (a mostly-solvable Sudoku, a reasonably-sized N-Queens board), the difference between checking constraints only at the end and checking them immediately after each placement is the difference between a search that finishes in milliseconds and one that never finishes within any practical time bound, even though both share the same worst-case big-O classification.

They demonstrate the same result reachable via two structurally different mechanisms -- Kahn's is fundamentally a greedy/BFS-flavored removal process (repeatedly peel off in-degree-zero nodes), while the DFS-based approach is a byproduct of DFS finish-order (reverse post-order). Having both reinforces that "a DAG has a linear order respecting every edge" is a property of the GRAPH, not an artifact of one specific algorithm's traversal strategy -- and the two also detect cycles through entirely different mechanisms (a short output vs. a back-edge), which is a useful cross-check when debugging.

A FULLY sorted structure (like a balanced BST) would also give O(log n) access to the minimum, but maintaining full order at every level costs more work per insertion than a heap's local parent-child property requires. The heap property is the MINIMUM invariant needed to guarantee "the root is always the extreme value" -- deliberately not maintaining any stronger ordering is exactly what keeps push/pop at O(log n) instead of paying for a guarantee (full sortedness) that heap operations never actually need.