Decoder

An upper bound on how cost grows with input size n. Drop constants and lower-order terms - as n → ∞ only the fastest-growing part matters, so O(2n + 3) and O(n) are the same class.

Example: O(n² + 100n) → O(n²) - read: order n squared.

Used in: DSA · Complexity & Big-O

Cost doesn't grow with n at all - one array index, one hash lookup.

Example: arr[i] is O(1) - read: order one.

Used in: DSA · Complexity & Big-O

Cost grows by one step each time the input DOUBLES - halving each step, as in binary search or a balanced tree.

Example: Binary search on 1,000,000 items ≈ 20 comparisons.

Used in: DSA · Complexity & Big-O, DSA · Master theorem

The cost of a good comparison sort: n passes, each doing log n work (or log n passes, each doing n work). The floor no comparison-based sort can beat.

Example: log₂(n!) ≈ n log n - the lower bound proof for any comparison sort.

Used in: DSA · Sorting & Searching

Nested loops over the same input - for each of n items, look at all n again. Bubble sort; a naive worst-case quicksort pivot.

Example: O(n² + n) is just O(n²) - the lower-order term is dropped.

Used in: DSA · Complexity & Big-O

Cost doubles with every extra item - enumerating all subsets, naive recursive Fibonacci. At n = 1,000,000 this is more operations than there are atoms in the observable universe.

Example: fib(n) branching into two calls at each of n levels → O(2ⁿ).

Used in: DSA · Complexity & Big-O

Cost is every possible ORDERING of n items - brute-force travelling salesman, all permutations. There are n! of them, and a comparison sort must be able to tell any two apart.

Example: n! possible orderings of n elements; log₂(n!) ≈ n log n comparisons needed to distinguish them all.

Used in: DSA · Complexity & Big-O, DSA · Sorting & Searching

The cost of touching every vertex and every edge once - BFS, DFS, topological sort. V and E are added, not multiplied, because a traversal visits each exactly once.

Example: Breadth-first search over a graph runs in O(V+E).

Used in: DSA · Graphs

V and E multiplied rather than added - every vertex re-examines every edge, as in Bellman-Ford's relax-all-edges, V-1 times.

Example: Bellman-Ford shortest paths: O(V·E).

Used in: DSA · Graphs

Cost measured AVERAGED over a sequence of operations, even when one step is occasionally expensive. A dynamic array append is normally O(1), but doubling the backing store when full is an O(n) step - because capacity doubles geometrically, that rare expensive step is paid for by the many cheap ones.

Example: Python list.append(), Go slice append - amortized O(1) even though the occasional resize is O(n).

Used in: DSA · Complexity & Big-O, DSA · Complexity theory

A TIGHT bound - both the upper (O) and lower (Ω) bounds match. This is the ACTUAL growth rate, not merely a ceiling. People say "O(n)" casually but usually mean Θ(n).

Example: Quicksort is Θ(n log n) on average, but only O(n²) - not Θ(n²) - in the worst case.

Used in: DSA · Complexity & Big-O, DSA · Master theorem

A LOWER bound (the floor) on how cost grows - the algorithm can't do better than this, no matter how favorable the input.

Example: O is an upper bound (ceiling), Ω a lower bound (floor), Θ a tight bound (both match).

Used in: DSA · Complexity & Big-O

Grows so slowly it's effectively a constant for any input size that could ever exist - under 5 for any n you'd actually see. Shows up as the near-O(1) cost of union-find with path compression.

Example: Union-find operations: O(α(n)) - practically constant time.

Used in: DSA · Graphs, DSA · Complexity theory

A divide-and-conquer algorithm splits into a subproblems of size n/b, plus f(n) work to divide and combine. The master theorem solves this by comparing f(n) against n^(log_b a), the total work at the leaves of the recursion tree.

Example: Merge sort: T(n) = 2·T(n/2) + O(n) → Θ(n log n).

Used in: DSA · Complexity theory

The set of decision problems solvable in polynomial time - the "efficiently solvable" problems.

Example: P ⊆ NP - every problem solvable in polynomial time is also verifiable in polynomial time.

Used in: DSA · Complexity theory

Decision problems whose solutions are VERIFIABLE in polynomial time, even if finding one isn't known to be fast.

Example: NP-complete = NP ∩ NP-hard - the hardest problems within NP.

Used in: DSA · Complexity theory

In NP (solutions verifiable in polynomial time) AND NP-hard (every NP problem reduces to it) - the hardest problems within NP itself.

Example: NP-complete = NP ∩ NP-hard.

Used in: DSA · Complexity theory

At least as hard as NP-complete, but not necessarily IN NP - it might not even have a polynomial-time-verifiable solution. All NP-complete problems are NP-hard; some NP-hard problems are harder still.

Example: The halting problem is NP-hard and undecidable - no algorithm solves it at all.

Used in: DSA · Complexity theory

The number of ways to pick an unordered group of k items from n - used to size a shuffle-sharding blast radius: split N workers into groups of k, and C(N,k) is how many distinct shard combinations exist.

Example: C(8,2) = 28 possible shuffle shards from 8 workers split into pairs - a 1-in-28 blast radius per customer.

Used in: System Design · Amazon case study

n × (n−1) × (n−2) × ... × 1 - the number of ways to ORDER n distinct items. The size of the search space a comparison sort or brute-force permutation search has to distinguish.

Example: log₂(n!) ≈ n log n - the information-theoretic lower bound on comparison sorts.

Used in: DSA · Sorting & Searching, DSA · Complexity & Big-O

There are 2ⁿ subsets of an n-element set; if generating or scoring each one costs O(n), the total is O(n·2ⁿ). One factor for HOW MANY subsets, one for the per-subset cost.

Example: Iterative-cascade and bitmask solutions to the subsets problem: both O(n·2ⁿ).

Used in: DSA · Subsets

n·W distinct DP states (items × capacities), O(1) work to fill each. Called "pseudo-polynomial" because it's polynomial in the numeric VALUE of W, not in W's number of digits - fine for a small capacity, blows up if W is astronomically large.

Example: 0/1 knapsack: O(n·W) states, O(1) each, replacing an exponential 2ⁿ brute force.

Used in: DSA · Dynamic programming

A DP over two sequences of length n and m fills an n×m table of states, O(1) work per cell - longest common subsequence, edit distance. Replaces an exponential brute force of trying every subsequence.

Example: LCS: n·m states (prefix-length pairs), O(1) work each → O(n·m), versus naive O(2ⁿ).

Used in: DSA · Dynamic programming

Finding the k largest/smallest of n items with a size-k heap: one O(log k) heap operation per item, n items - far cheaper than sorting everything (O(n log n)) when k is small.

Example: "k largest," "merge k lists," "running median": a size-k heap gives O(n log k) instead of sorting everything.

Used in: DSA · Interview patterns, DSA · Clinic 20 (top-k frequent)

A recursion tree that branches into k calls at each of d levels has kᵈ total calls - the general shape behind exponential blowups like naive Fibonacci (k=2).

Example: "branching into k calls per level over depth d gives O(kᵈ)."

Used in: DSA · Complexity & Big-O

x ∈ S means x is a member of the set S.

Example: P ⊆ NP - every element of P is also in NP.

Used in: DSA · Complexity theory

Every element of the left set is also in the right set - the sets may be equal. (⊂, without the underline, means a PROPER subset - the sets can't be equal.)

Example: P ⊆ NP, NP ⊆ NP-hard's reach conceptually - the containment hierarchy complexity theory is built on.

Used in: DSA · Complexity theory

The elements two sets have in common.

Example: NP-complete = NP ∩ NP-hard.

Used in: DSA · Complexity theory

chalk's single most-used piece of notation. In a function or data structure it means "maps to" (input → output, key → value). In a causal or sequential chain it means "leads to" or "then" (arrivals rise → backlog grows). Same glyph, read differently by context - that's exactly what this page is for.

Example: A neural net learns the mapping input → output. A cache miss → a database read → a slower response.

Used in: Everywhere - AI, DSA, System Design, Data Systems

True for every x in the domain, no exceptions. chalk's lessons write this out as "for all" in prose rather than using the glyph, but it's the standard symbol for exactly that phrase.

Example: "For all n, a comparison sort needs at least log₂(n!) comparisons" - a for-all claim, written ∀n.

Used in: DSA · proofs and lower bounds (written in words, not the glyph)

True for AT LEAST one x in the domain - you only need to find one. chalk's prose spells this out as "there exists" rather than using the glyph.

Example: "There exists a Nash equilibrium for every finite game" (Nash's theorem) - an existence claim, written ∃.

Used in: Game Theory (written in words, not the glyph)

The two sides imply each other in BOTH directions - each is true exactly when the other is. Stronger than a plain "if", which only claims one direction.

Example: A Nash equilibrium exists iff every player is playing a best response to everyone else.

Used in: Game Theory, Data Systems (written as "iff" or spelled out, not the glyph)

How likely event A is, from 0 (never) to 1 (certain).

Example: P(region outage) - the input to a reliability calculation.

Used in: System Design, Psychology · Decision-making under uncertainty

The probability-weighted average outcome - what you'd get on average over many repeated trials, not the outcome of any single one. A positive-EV choice is correct even when it loses this time.

Example: EV = Σ (probability × outcome). A coin flip paying +$150 heads / −$100 tails: EV = .5(150) + .5(−100) = +$25.

Used in: Personal Development · Mental models, Psychology · Decision-making under uncertainty, AI · RL reward

Add up a series of terms, one per value of the index. Shows up identically in expected-value math and in an unrelated context - total pattern length across many patterns in a multi-string search.

Example: EV = Σ(probability × outcome). Aho-Corasick multi-pattern search: O(n + Σpattern + matches).

Used in: Personal Development, Psychology, DSA · Finding the needle (string search), AI · weighted sum

NOT the circle constant - a different π entirely, used here for a function that distorts raw probabilities into the SUBJECTIVE weight a decision actually gets. People over-weight rare events (jackpots, plane crashes) and under-weight likely ones, and a sure thing (p=1) gets an extra premium (the certainty effect).

Example: "Probability weighting π(p). We don't use raw probabilities."

Used in: Psychology · Decision-making under uncertainty

How fast requests/orders/items ARRIVE, in items per unit time - the input side of a queue.

Example: L = λ · W - Little's Law. If λ rises and you can't cut W, the backlog L grows without bound.

Used in: System Design · The order slip rail

How fast ONE server (one worker, one kitchen station) can process items, in items per unit time - the capacity side of a queue. With N servers, the system's total capacity is Nμ; once λ exceeds it, there's no steady state and the wait grows without bound.

Example: N workers at service rate μ each, one arrival stream at rate λ: avg_wait stays flat while λ < Nμ, then takes off past it.

Used in: System Design · The order slip rail

The average number of items IN the system (L) equals the arrival rate (λ) times the average time each item spends in the system (W). It's an identity - always true for a stable system, not a heuristic or a tunable - which is why you can't queue your way out of arrivals exceeding capacity.

Example: If λ rises and W can't fall, L (the backlog) must grow proportionally.

Used in: System Design · The order slip rail

Half of requests finish faster than this, half slower. The typical case - but a system can have a great p50 and a terrible tail.

Example: Discord: p50 read latency dropped from 500ms to under 100ms after re-sharding.

Used in: System Design · Discord case study

99% of requests finish at or below this time - the other 1% (the tail) is often where GC pauses, hot partitions, and retries live. A system's p99 can be 10x its p50 even when the average looks fine.

Example: Instagram's RocksDB swap took Cassandra's p99 from 60ms to 20ms.

Used in: System Design · Instagram case study, System Design · Discord case study, System Design · Cloudflare case study

One request in a thousand is slower than this - the extreme tail, where the worst-case coordination and contention costs surface.

Example: Cloudflare's global config propagation: p99 = 2.29 seconds to reach every machine on Earth.

Used in: System Design · Cloudflare case study

The naive way to assign a key to one of N partitions: hash it and take the remainder. Flagged as an anti-pattern in chalk's own Data Systems notes - changing N (adding or removing a shard) remaps almost every key, forcing a massive reshuffle. Consistent hashing exists to fix exactly this.

Example: "✗ hash mod N - the anti-pattern: changing N remaps almost every key."

Used in: Data Systems · Partitioning

The direction of STEEPEST INCREASE of a function over its inputs. Gradient descent steps the opposite way - downhill - to reduce loss. chalk's own lessons write the update rule out in words rather than the glyph, but ∇ is the standard shorthand for exactly the quantity they call "the gradient."

Example: w = w − learning_rate × gradient - in symbol form, w ← w − η∇L.

Used in: AI · How it learns (loss, gradient descent, backprop)

Not the maximum VALUE - the INPUT that produces it. argmax over token probabilities means "pick the token with the highest probability," not the probability itself.

Example: Greedy decoding: always take the highest-probability token (argmax) - deterministic, but repetitive and flat.

Used in: AI · Inference

Turns a list of raw scores into a probability distribution - every output is positive and they all sum to 1. The "soft" version of argmax: instead of picking one winner outright, it weights every option by how much it deserves relative to the rest.

Example: Attention(Q, K, V) = softmax(Q·Kᵀ / √dₖ) · V - softmax turns relevance scores into attention weights.

Used in: AI · Attention and the transformer

The core of attention's relevance score: each token's Query is matched against every other token's Key via a dot product. The ᵀ (transpose) flips K's rows into columns so the multiplication lines up - the result is an n×n matrix of "how relevant is every token to every other token."

Example: Attention(Q, K, V) = softmax(Q·Kᵀ / √dₖ) · V.

Used in: AI · Attention and the transformer

dₖ is the dimensionality of the Key vectors; dividing by its square root keeps the dot-product scores from growing too large as dimensions increase, which would otherwise push softmax into a near-one-hot, numerically unstable region.

Example: ÷√dₖ keeps Attention(Q, K, V) = softmax(Q·Kᵀ / √dₖ)·V numerically stable.

Used in: AI · Attention and the transformer

The model currently being trained, viewed as a function that picks a response y given a prompt x. Same glyph as the circle constant, completely different meaning - chalk's own RLHF notes never use π for 3.14159 at all, only for this.

Example: maximize E[r(x,y)] − β·KL(π ‖ π_ref) - π is the policy being trained.

Used in: AI · Fine-tuning and alignment (RLHF)

The frozen starting point (usually the supervised-fine-tuned model) that the trained policy π is penalized for drifting too far from - the anchor that keeps RLHF from reward-hacking into gibberish that merely scores well.

Example: KL(π ‖ π_ref) measures how far the trained policy has drifted from this frozen reference.

Used in: AI · Fine-tuning and alignment (RLHF)

A measure of how far one probability distribution has drifted from another - here, how far the trained policy has wandered from its frozen starting point. Added as a penalty so an RL loop can't max out a reward model by drifting off-distribution into gibberish ("reward hacking").

Example: maximize E[r(x,y)] − β·KL(π ‖ π_ref).

Used in: AI · Fine-tuning and alignment (RLHF)

A knob on how tightly the KL penalty leashes the trained policy to the reference policy - bigger β keeps the model closer to its starting point; smaller β lets it drift further in pursuit of reward.

Example: β·KL(π ‖ π_ref) - β tunes how tight that leash is.

Used in: AI · Fine-tuning and alignment (RLHF)

Close enough to treat as equal for the point being made - not exact.

Example: "~4 English characters ≈ 1 token" - the rule of thumb for estimating LLM token counts from character counts.

Used in: AI · Tokens and embeddings, AI · How it learns

The two sides are different - often used to warn that two things people conflate are NOT the same.

Example: "Confidence ≠ correctness" - fluency is not evidence an LLM's answer is right.

Used in: AI · Inference

The left side is no bigger than the right - includes the equal case, unlike a strict <.

Example: Fencing tokens: storage "rejects any write carrying a token ≤ that" it has already accepted.

Used in: Data Systems · The trouble with distributed systems

The left side is at least the right - includes the equal case.

Example: Write skew: the invariant "≥1 doctor on call" can still be violated when two transactions each read "2 on call, fine to leave" and both leave.

Used in: Data Systems · Transactions

Unboundedly large - used in Big-O to describe the LIMIT being taken: as n grows without bound, only the fastest-growing term of a cost function matters.

Example: "As n → ∞ only the fastest-growing part matters" - why Big-O drops constants and lower-order terms.

Used in: DSA · Complexity & Big-O

Either direction from a value - a tolerance, or (in a balance factor) a signed deviation whose sign doesn't matter, only its magnitude.

Example: An AVL tree's balance factor is kept within {−1, 0, +1}; the first node whose factor hits ±2 gets rotated.

Used in: DSA · Trees

Straightforward division - shows up in both throughput math and the attention formula's stabilizing scale-down.

Example: "decode floor: 7 ms/token → 3.5 ms → 1.75 ms (bandwidth-bound: bytes ÷ 2 TB/s)."

Used in: AI · Inference at scale, AI · Attention and the transformer

Two things that always hold together - true exactly when the other is, or one is DEFINED to be the other in a special case.

Example: A* with heuristic h ≡ 0 degenerates exactly into Dijkstra's algorithm. "Can finish ≡ no cycle" for course scheduling.

Used in: DSA · Shortest paths worked, DSA · Clinic 16 (course schedule)

One quantity grows in lockstep with another (or with its reciprocal) - the exact ratio doesn't matter, only that they move together.

Example: Fixed-number-of-partitions rebalancing: "partitions ∝ nodes." Provider routing: "weight ∝ 1/price²."

Used in: Data Systems · Partitioning, System Design · OpenRouter case study