Every page on this site leans on a stock of jargon — "amortized," "invariant," "exchange
argument," "tail call" — on the assumption that a reader already knows it, because stopping to
define it fresh on every page would drown the actual algorithm. This page is where that
assumption gets paid off: thirty terms, each with a short definition and a link to the specific
page on this site that earns it — not a generic textbook restatement, the real sentence (or
demo, or measurement) on this site that uses the term correctly. Type below to filter by term or
definition.
Growth & cost
Asymptotic notation (Big-O, Big-Θ, Big-Ω)
A way of describing how an algorithm's cost scales as input size n grows,
ignoring constant factors and lower-order terms — O is an upper bound, Ω
a lower bound, Θ both at once (a "tight" bound). Two algorithms in the same
Big-O class can still run at very different real speeds; see constant
factor below. How Fast Is Big-O, Really?
translates every common class into real operation counts and wall-clock time at several sizes of
n.
Worst-case vs. average-case vs. expected
Three different promises a complexity bound can make: worst-case holds for every
input, average-case is a mean over some assumed input distribution, and expected describes a
randomized algorithm's own coin flips rather than the input at all. Quicksort is the site's clearest example of the gap: its
own Complexity section documents O(n²) on an already-sorted array against a
naive last-element pivot, next to an average/expected O(n log n) that holds for
almost every real input.
Amortized (cost)
A per-operation cost bound that holds only once averaged over a long enough sequence of
operations, not on every single call — an individual call can cost far more than the amortized
figure, as long as cheaper calls around it make up the difference. Dynamic Array's doubling growth is the canonical
example: any single push that triggers a resize costs O(n), but that
cost is paid rarely enough that the amortized cost per push is still
O(1). Amortized Analysis, Explained
works through the three standard proof techniques against real examples.
Potential function
One of the three standard ways to prove an amortized bound: define a single number
Φ summarizing how much "stored-up debt" a data structure's current state is
carrying, such that an expensive operation is paired with a large drop in Φ and
cheap operations let it build back up. Amortized Analysis, Explained reproduces Splay Tree's own potential function
(Φ = Σ log₂(size(v))) against a real rotation, with the actual before/after
numbers.
Constant factor
The part of an algorithm's real running cost that Big-O notation deliberately throws away —
two algorithms in the identical complexity class can still differ by a measured multiple in
practice, for reasons (cache behavior, allocation, branch count per step) the asymptotic bound
never claimed to capture. Min-Max
Heap's own Complexity section is a worked example of why this needs measuring, not
reasoning from shape alone: a plausible-sounding "half the comparisons" claim from the structure's
two-levels-per-step design turned out backwards once actually instrumented against Binary Heap.
Recurrence relation
An equation defining a function's cost in terms of its own cost on smaller inputs — the
standard way to express a divide-and-conquer algorithm's running time before solving it into a
closed form. T(n) = a·T(n/b) + f(n) is the shape the Master Theorem solves directly; a recurrence whose
subproblem count or size depends on the data itself (Quicksort's uneven pivot splits) doesn't fit that shape at
all.
Regularity condition
A technical side-requirement of the Master Theorem's Case 3 (a·f(n/b) ≤
c·f(n) for some constant c < 1) that's automatically satisfied for
any plain polynomial f(n) — which is every recurrence this site actually uses — but
is a real, separate check for a non-polynomial combine cost. The Master Theorem, Explained names the one
textbook recurrence (T(n) = 2T(n/2) + n/log n) where skipping it would matter.
Design techniques
Divide and conquer
Split a problem into independent subproblems of the same shape, solve each recursively, then
combine their results — the pattern a recurrence relation
describes and the Master Theorem solves. Distinct from
dynamic programming in that the subproblems here don't
overlap — nothing needs to be cached, because nothing gets solved twice.
Dynamic programming
Solve a problem by combining answers to overlapping subproblems, solving each
distinct subproblem exactly once and reusing the answer every other time it's needed — either by
filling a table bottom-up or by memoizing top-down recursion. Choosing a Dynamic Programming
Approach funnels all eleven of the site's DP entries down to one of four subproblem shapes
(two sequences, capacity vs. positional, tree-node, digit-position) rather than treating each as a
new technique.
Memoization
Caching the result of a recursive call keyed by its arguments, so that calling it again with
the identical arguments returns the cached answer instead of recomputing — the top-down way to get
dynamic programming's "solve each subproblem once" guarantee
without filling a table by hand. Edit
Distance's demo lets you switch between plain bottom-up table-filling and top-down memoized
recursion against the identical recurrence, with unfilled cells visibly staying unfilled in the
memoized version.
Greedy algorithm
An algorithm that commits to the locally best-looking choice at each step and never
reconsiders it — fast, but only correct when something about the problem's structure
guarantees a local best choice can't be beaten by looking further ahead. Choosing a Greedy Strategy sorts the site's
greedy entries into four trust tiers by exactly what kind of proof (or lack of one) backs that
guarantee, from exchange argument down to "never exact, but
provably bounded."
Exchange argument
A proof technique for a greedy algorithm's correctness: take any optimal solution that differs
from the greedy one, show it can be transformed into the greedy choice by swapping two elements
without making it worse, and conclude the greedy choice is at least as good. The strongest of the
four trust tiers in Choosing a Greedy
Strategy, which further splits it into single-item substitution, adjacent-swap,
cancellation-pair, and no-wasted-proposal variants across the site's real entries.
Backtracking
Build a candidate solution incrementally, check at each step whether the partial candidate is
still legal, and undo the last choice and try another the moment it isn't — rather than building
every full candidate and checking only at the end. Choosing a Backtracking Strategy sorts
nine entries by what actually makes a partial candidate illegal, since that's what varies between
them, not the undo mechanism itself.
Pruning
Cutting off a search branch early, once it's provable (or merely likely) that nothing useful
can come from continuing down it, instead of exploring it to the end. Doesn't change an
exponential algorithm's worst-case order, but can cut its real constant factor dramatically: N-Queens' own demo counts 3,125 candidate boards
with no pruning at all on a 5×5 board, against 220 with it.
Heuristic
An estimate used to guide a search toward a promising direction faster, without itself being
guaranteed correct — a heuristic that never overestimates the true remaining cost is
called admissible, and an admissible heuristic is what lets A* Search find the exact same cheapest path as Dijkstra's
Algorithm while visiting far fewer cells. The same page's Pitfalls section shows what breaks (a
wrong, non-admissible answer, not just a slower one) when the heuristic lies.
Pivot
The single element a partitioning step picks to split the rest of the data around — everything
smaller goes to one side, everything larger to the other, and the pivot itself lands in its final
position. Quicksort's own demo lets you compare pivot
strategies directly and see how a bad one (always picking the last element of an already-sorted
range) degrades the split from roughly-even to one-element-at-a-time.
Randomness & hardness
Randomized algorithm
An algorithm whose own behavior depends on random choices it makes internally, not just on its
input — meaning its running time or correctness is a claim about probability, not a guarantee for
every run. Las Vegas vs. Monte Carlo splits
every randomized entry on this site by which of the two things (time or correctness) the
randomness is allowed to gamble with.
Las Vegas vs. Monte Carlo
Two opposite trade-offs a randomized algorithm can make: a Las Vegas
algorithm (Quickselect, Welzl's Smallest Enclosing Circle) is always correct and gambles only
on running time; a Monte Carlo algorithm (Karger's Algorithm, Miller-Rabin) finishes in guaranteed-fast
time and gambles on correctness instead. Las Vegas vs. Monte Carlo states the
distinction formally and shows how unevenly two real Monte Carlo error bounds shrink under
repetition.
NP-hard / NP-complete
A problem is NP-hard if no algorithm is known (or, widely believed, exists) that solves every
instance of it in polynomial time — NP-complete additionally requires the problem to sit inside NP
itself (a candidate solution can be checked quickly, even if finding one can't). Labeling a problem
this way isn't the end of the discussion: NP-Hard: Now
What? lines up four genuinely different things the site's nine NP-hard/NP-complete entries do
about it — restrict into P, stay exact in pseudo-polynomial time, trade exactness for a proven
ratio, or accept exponential time and win only on constant factor.
Approximation ratio
A proven bound on how far an approximation algorithm's answer can be from the true optimum —
not a typical-case hope, a worst-case guarantee that holds for every input, which is what
separates it from an ordinary unproven heuristic that merely tends to do
well. NP-Hard: Now What? names two
site entries (Set Cover, Steiner Tree) that trade exactness for exactly this kind of proven
ceiling, and its Pitfalls section shows a real case where a plausible-looking heuristic
substitution quietly loses the guarantee entirely, not just some accuracy.
Structural properties
Invariant
A condition an algorithm guarantees stays true at a specific point in every iteration (often
"at the start of this step"), which is what makes the final answer provably correct rather than
merely plausible. Binary Search's own
invariant is stated explicitly: at the start of every step, if the target is anywhere in the
array, it's between lo and hi — which is exactly what each step's
narrowing has to preserve.
Load factor
The ratio of stored entries to available bucket slots in a hash-based structure — the single
number that governs the trade-off between memory use and collision frequency, and the number a
resize policy watches to decide when to grow. Hash Table's own demo displays the live
load factor on every operation and resizes once it crosses 0.75, the same threshold its Complexity
section cites as the reason put is only amortizedO(1), not worst-case O(1).
Stable sort
A sort that preserves the relative order of elements that compare as equal — meaningful only
when "equal" doesn't mean "identical" (sorting records by one field while silently caring about
another). Choosing a Comparison Sort
names it as one of the three decisive questions (alongside size and worst-case guarantee) that
separates the site's seven comparison sorts, not an afterthought property.
In-place
An algorithm that transforms its input using only a small, constant (or logarithmic) amount of
extra memory, rather than allocating a second structure the size of the input. Quicksort's own Complexity section names this
directly as its real advantage over Merge Sort's identical O(n log n) average case: no
merge buffers, because partitioning happens in place.
Idempotent (operation)
An operation that can be safely applied to the same input more than once without changing the
answer — min, max, and gcd qualify; sum,
count, and plain product don't. The distinction matters specifically for
structures that answer an overlapping range query by combining two overlapping
sub-ranges: Choosing a Range Query
Structure shows a non-idempotent op double-counts the overlap silently, which is exactly why
Sparse Table only works for the idempotent case and needs Fenwick Tree or Segment Tree otherwise.
Degenerate case
An input that's technically valid but defeats the data structure's usual performance
assumption — not a bug, a worst case the structure's own design doesn't protect against. Binary Search Tree's own Complexity
section names this exactly: O(log n) on average for randomly-ordered input, but
O(n) when the tree degenerates into a straight line — which is precisely the failure
mode AVL Tree and other self-balancing trees exist to
rule out.
Dense vs. sparse (graph)
A graph is dense when its edge count is close to the maximum possible (O(V²))
and sparse when it's closer to O(V) — the distinction that decides whether an
adjacency matrix or an adjacency list is the right representation, since a dense graph's matrix
wastes little space relative to the real edge count while a sparse graph's would be almost all
empty cells. Ford-Fulkerson's own demo
uses a dense V×V capacity matrix deliberately, naming adjacency lists as the
real choice for a sparse graph instead.
Topological order
An ordering of a directed acyclic graph's vertices such that every edge points from something
earlier in the order to something later — defined only when the graph has no cycle, since a cycle
would require some vertex to come before itself. Topological Sort's own DFS-based
construction gets this for free from a side effect: reversing the order nodes finish in during a
post-order DFS already satisfies the guarantee, with no extra bookkeeping.
Tail call
A recursive call that is the very last thing a function does before returning — the specific
shape a language spec can permit an engine to optimize into a plain loop, reusing the current
stack frame instead of pushing a new one. How Deep Can You Recurse? measures an
ordinary recursive function against one written in tail-call form live in your own browser, and
finds V8 doesn't actually implement the optimization the spec permits — both forms fail at the
same depth.
Online vs. offline algorithm
An online algorithm must answer each query as it arrives, with no knowledge of
future queries; an offline algorithm gets to see the entire batch of queries
upfront and can reorder or batch them before answering any. Online vs. Offline compares three real
pairs on this site that answer the identical question under each constraint, including one pair
(Offline LCA vs. Binary Lifting) where the offline version's advantage grows without bound as
n grows, independent of how many queries are asked.