A useful little glossary
Precise definitions for the concepts you will meet in the lectures. Follow a term back to its lesson for examples and context.
Algorithm
A finite, unambiguous procedure for solving a specified problem.
Explore in contextAmortized analysis
A bound on total cost over a sequence of operations, expressed per operation; no input probability distribution is required.
Explore in contextArray
An indexed sequence whose entries can be accessed directly. Its representation affects resizing and memory costs.
Explore in contextAsymptotic analysis
The study of how a cost function grows as input size becomes sufficiently large.
Explore in contextAverage case
Expected cost under an explicitly specified distribution of inputs of a fixed size.
Explore in contextBig O
An eventual upper bound up to a positive constant factor. It does not inherently mean worst case.
Explore in contextBig Omega
An eventual lower bound up to a positive constant factor.
Explore in contextBig Theta
A matching eventual upper and lower bound up to positive constant factors.
Explore in contextBinary search
Search of sorted data by repeatedly eliminating half of the remaining interval.
Explore in contextComponent
An equivalence class of mutually connected objects in the connectivity model.
Explore in contextCost model
The operations counted as a proxy for a resource such as execution time.
Explore in contextData structure
A representation of information together with operations for accessing or changing it.
Explore in contextDoubling ratio
The ratio T(2n)/T(n), used experimentally to estimate a power-law exponent.
Explore in contextFIFO
First in, first out: the removal order of a queue.
Explore in contextGCD
The greatest positive common divisor of two nonnegative integers not both zero.
Explore in contextGeneric type
A class or interface parameterized by a type, such as Stack<Integer>.
Explore in contextInvariant
A statement preserved by every relevant step of an algorithm.
Explore in contextIterator
An object that traverses a collection through operations such as hasNext and next.
Explore in contextLIFO
Last in, first out: the removal order of a stack.
Explore in contextLogarithm
The exponent needed to raise a specified base to a value; repeated halving produces logarithmic counts.
Explore in contextLoitering
Retaining an unnecessary reference to an object that could otherwise be reclaimed.
Explore in contextMonte Carlo simulation
An experiment using randomized trials to estimate or study a quantity.
Explore in contextPath compression
Redirecting visited union–find parent links toward a root to accelerate later searches.
Explore in contextPercolation
In the supplied grid model, the existence of an open path connecting the top to the bottom.
Explore in contextRecurrence
An equation or inequality describing a cost in terms of smaller instances.
Explore in contextRecursion
A procedure calling itself on another instance, with a stopping condition.
Explore in contextStable sort
A sort that preserves the relative order of equal-key records.
Explore in contextTilde notation
f(n) ~ g(n) means f(n)/g(n) tends to 1; the leading coefficient remains relevant.
Explore in contextUnion–find
A data structure maintaining disjoint components under merges and representative queries.
Explore in contextWorst case
The maximum cost among permitted inputs of a fixed size.
Explore in context