Algorithms and Complexity glossary

Clear, one-line definitions of the Algorithms and Complexity terms used across the OgbonLab textbooks. Each entry links to the interactive sections where the idea is taught.

bfs tree

The tree produced by breadth-first search rooted at a start vertex; each non-root vertex's parent is the neighbor that first discovered it.

binomial theorem

(x + y)^n = Σ_{k=0}^n C(n,k) x^(n-k) y^k; expands a binomial power as a sum of monomials weighted by binomial coefficients.

chain

In a partially ordered set, a totally ordered subset; every two elements of a chain are comparable.

decision problem

A computational problem whose answer is yes or no, formalized as deciding membership in a language L ⊆ {0,1}*.

decision tree

A rooted tree whose internal nodes are tests on inputs and whose leaves are outputs; used as a model of comparison-based computation and in machine learning.

See: Decision Trees, Decision Tree Practice with Python

degree of an extension

For a field extension L/K, the dimension [L:K] of L as a vector space over K.

dijkstra

A greedy algorithm computing shortest paths from a source in a graph with non-negative edge weights, running in O((V+E) log V) with a binary heap.

graph

A pair G = (V, E) of vertices V and edges E ⊆ V × V (or unordered pairs); the basic object of graph theory and many algorithms.

halting problem

The problem of deciding, given a Turing machine M and input w, whether M halts on w; proved undecidable by Turing in 1936.

master theorem

A formula giving the asymptotic solution of recurrences T(n) = aT(n/b) + f(n) by comparing f(n) to n^(log_b a).

maximal element

In a partially ordered set, an element m with no element strictly greater than it; not necessarily a maximum.

merge sort

A divide-and-conquer sorting algorithm with O(n log n) worst-case time; recursively splits the list and merges sorted halves.

np-complete

A decision problem in NP to which every NP problem reduces in polynomial time; the hardest problems in NP, e.g. SAT, 3-COLOR.

np-hard

A problem at least as hard as every problem in NP under polynomial-time reduction; need not itself lie in NP.

pascal recurrence

The identity C(n,k) = C(n-1,k-1) + C(n-1,k); each binomial coefficient is the sum of the two directly above it in Pascal's triangle.

quicksort

A divide-and-conquer sorting algorithm that partitions around a pivot; expected O(n log n) time, worst case O(n²).