Tauseef FayyazA to Z
Glossary
Every concept in this sheet, plus the smaller terms it uses. Select a concept to open its card.
A
- Amortised cost
- The average cost per operation over any long sequence of operations, even if a few single operations are expensive.
- Arrays and dynamic arrays
- An array stores items side by side in memory, so reading or writing index i is O(1).
B
- Best, worst and average case
- Worst case is the most work on any input of size n, best case the least, and average case the expected work over typical or random inputs.
- Big-O notation
- Big-O describes how the running time or memory of an algorithm grows as the input size n grows, keeping only the fastest-growing term and dropping constants.
C
- Common growth rates
- From fastest to slowest: O(1) constant, O(log n) repeated halving, O(n) one pass, O(n log n) sorting, O(n^2) all pairs, O(2^n) all subsets, O(n!) all orderings.
- Composite and custom keys
- When a key is made of several values, like a grid cell or a sorted word, it must be hashable and compare by value.
- Counting operations in loops
- Multiply the costs of nested loops and add the costs of loops in sequence.
H
- Hash maps
- A hash map stores key-value pairs in buckets chosen by a hash of the key, giving O(1) average insert, lookup and delete.
- Hash sets
- A hash set stores unique keys without values, with O(1) average add, remove and membership check.
I
- Integer limits and overflow
- Java and C++
intholds up to about 2.1 billion (2^31 - 1); past that Java wraps around and C++ has undefined behaviour.
J
- JavaScript built-in collections
- Arrays are dynamic arrays with O(1)
pushandpopat the end.
P
- Prefix sums
- A prefix sum array stores running totals, so
prefix[i]is the sum of the first i items.
R
- Reading constraints
- The input limits in a problem hint at the expected complexity.
S
- Space complexity and the call stack
- The extra memory an algorithm uses beyond its input, as a function of n.
- Strings
- A string is a sequence of characters.