Glossary

Describes how an algorithm’s runtime or memory grows with input size.

A measure of how runtime scales with input size.

How much extra memory an algorithm needs as n grows.

A function that calls itself to solve smaller subproblems.

Caching results of expensive calls to avoid recomputation.

Split a problem into smaller pieces, solve them, then combine.

A sort that preserves the relative order of equal keys.

Key/value store with average O(1) operations.

Average cost per operation over a sequence, even if some are expensive.