Algorithm Analysis and Asymptotic Notation: every key term you need (+ practice quiz)
25 flashcard terms for Data Structures & Algorithms Topic 1, written to match the course framework. Study them here, then drill them as interactive flashcards, or test yourself with the 15-question quiz — free, no account needed.
An asymptotic upper bound: f(n) is O(g(n)) when constants c and n0 exist such that f(n) is at most c times g(n) for every n at or above n0. It caps growth, so it may be loose.
Big-Omega notation
An asymptotic lower bound: f(n) is Omega(g(n)) when f(n) is at least c times g(n) for all sufficiently large n. Used to argue that an algorithm cannot beat a given cost.
Big-Theta notation
A tight asymptotic bound holding when a function is both O(g(n)) and Omega(g(n)), so it grows at the same rate as g up to constant factors. Merge sort is Theta(n log n) on every input.
Little-o notation
A strictly weaker upper bound: f(n) is o(g(n)) when the ratio of f to g tends to zero, meaning the bound holds for every positive constant c rather than for one. So n is o(n log n).
Amortized analysis
Averaging the cost of an operation over a worst-case sequence of operations rather than over random inputs. It gives a guaranteed per-operation bound even when individual calls are expensive.
Aggregate method
An amortized technique that bounds the total cost of n operations and divides by n. Used to show that n pushes on a doubling array cost O(n) total, so O(1) each on average.
Potential method
An amortized technique that assigns a potential to the structure and defines amortized cost as actual cost plus the change in potential. Valid when potential never falls below its starting value.
Worst-case running time
The maximum number of steps over all inputs of a given size. It is the standard guarantee reported for an algorithm because it holds no matter what adversarial input arrives.
Average-case running time
Expected cost under an assumed input distribution, usually uniform. Quicksort is famously Theta(n log n) on average but quadratic on its worst input under a fixed pivot rule.
Best-case running time
The minimum cost over inputs of a size, such as insertion sort finishing in linear time on already sorted data. It is rarely a useful guarantee on its own.
Input size parameter
The measure n against which cost is expressed: element count for a list, vertices and edges for a graph, or bit length for numeric problems where value and length differ sharply.
Basic operation counting
Choosing one representative operation, such as a key comparison or array write, and counting how often it runs. Constant work per iteration makes the count proportional to real time.
Constant time
Cost written O(1) that does not grow with input size, such as reading an array cell by index or pushing onto a stack backed by a preallocated buffer.
Logarithmic time
Cost written O(log n), typical of algorithms that discard a constant fraction of the remaining search space each step, such as binary search on a sorted array.
Linearithmic time
Cost written O(n log n), the bound achieved by merge sort and heapsort and the proven optimum for comparison sorting in the worst case.
Quadratic time
Cost written O(n squared), typical of nested loops over the same collection, as in insertion sort or a naive all-pairs comparison. It becomes painful near a million elements.
Exponential time
Cost growing like a constant raised to n, as in enumerating every subset of a set. Practical only for small n, which motivates dynamic programming and pruning.
Auxiliary space
Extra memory an algorithm uses beyond the input itself, including recursion stack frames. Merge sort needs linear auxiliary space while heapsort needs only a constant amount.
In-place algorithm
An algorithm that transforms its input using only constant or logarithmic extra space. Heapsort and the classic partition step of quicksort qualify under the usual definition.
Master theorem
A recipe solving recurrences of the form T(n) equals a times T(n over b) plus f(n) by comparing f with n raised to log base b of a, yielding one of three closed-form cases.
Recurrence relation
An equation defining a running time in terms of the same function on smaller inputs, the natural description of a recursive algorithm before it is solved into closed form.
Recursion tree method
Solving a recurrence by drawing the call tree, summing the work at each level, and multiplying by the number of levels. It usually gives a good guess to verify formally.
Substitution method
Guessing a closed-form bound for a recurrence and proving it by induction on n, strengthening the hypothesis with a lower-order term when the naive guess fails to carry through.
Loop invariant
A property true before a loop starts, preserved by each iteration, and strong enough at termination to imply correctness. It is the standard proof device for iterative algorithms.
Asymptotic growth ordering
The ranking of common functions by eventual dominance: constant, then log n, then n, then n log n, then polynomials, then exponentials, then factorial growth.