ARTICLE · Analysis
Complexity cheat-sheet
Lower bound for comparison sorts: Omega(n log n). Counting/radix/bucket beat it by not comparing.
(a) Data structure operations (average / worst)#
| Structure | Access | Search | Insert | Delete | Space | Notes |
|---|---|---|---|---|---|---|
| Array (static) | O(1) | O(n) | O(n) | O(n) | O(n) | insert/delete = shift |
| Dynamic array (JS Array) | O(1) | O(n) | O(1) amortized push; O(n) unshift/splice | O(1) pop; O(n) shift/splice | O(n) | doubling growth |
| Singly linked list | O(n) | O(n) | O(1) at head (with ref) | O(1) at head (with ref) | O(n) | no random access |
| Doubly linked list | O(n) | O(n) | O(1) with node ref | O(1) with node ref | O(n) | LRU backbone |
| Hash map / set (Map, Set, object) | — | O(1) avg / O(n) worst | O(1) avg | O(1) avg | O(n) | worst = all collide |
| BST (balanced: AVL, red-black) | O(log n) | O(log n) | O(log n) | O(log n) | O(n) | in-order = sorted |
| BST (unbalanced) | O(h) up to O(n) | O(n) | O(n) | O(n) | O(n) | degenerates to list |
| Binary heap | O(1) peek | O(n) | O(log n) | O(log n) pop | O(n) | heapify O(n) |
| Trie | — | O(L) | O(L) | O(L) | O(alphabet * total chars) | L = word length |
| Graph adjacency list | — | O(deg(v)) edge check | O(1) | O(deg) | O(V + E) | sparse graphs |
| Graph adjacency matrix | O(1) edge check | O(1) | O(1) | O(1) | O(V^2) | dense graphs; O(V) neighbors |
| Stack / queue (array / deque) | O(1) top | O(n) | O(1) | O(1) | O(n) | JS shift is O(n): use head index |
| Union-Find | — | O(alpha(n)) find | O(alpha(n)) union | — | O(n) | path compression + rank |
(b) Sorting algorithms#
| Algorithm | Best | Average | Worst | Space | Stable | Notes |
|---|---|---|---|---|---|---|
| Bubble | O(n) | O(n^2) | O(n^2) | O(1) | yes | never in practice |
| Insertion | O(n) | O(n^2) | O(n^2) | O(1) | yes | small n, nearly sorted, online |
| Selection | O(n^2) | O(n^2) | O(n^2) | O(1) | no | minimal swaps |
| Merge | O(n log n) | O(n log n) | O(n log n) | O(n) | yes | linked lists, external sort |
| Quick | O(n log n) | O(n log n) | O(n^2) | O(log n) stack | no | random pivot; cache-friendly |
| Heap | O(n log n) | O(n log n) | O(n log n) | O(1) | no | guaranteed, in-place |
| Counting | O(n + k) | O(n + k) | O(n + k) | O(k) | yes | small integer range k |
| Radix | O(d(n + b)) | O(d(n + b)) | O(d(n + b)) | O(n + b) | yes | d digits, base b; fixed-width keys |
| Bucket | O(n + k) | O(n + k) | O(n^2) | O(n) | yes | uniformly distributed floats |
TimSort (JS Array.prototype.sort) | O(n) | O(n log n) | O(n log n) | O(n) | yes (ES2019+) | merge + insertion hybrid; runs |
Lower bound for comparison sorts: Omega(n log n). Counting/radix/bucket beat it by not comparing.
(c) Common recurrences#
| Recurrence | Resolves to | Example |
|---|---|---|
| T(n) = T(n/2) + O(1) | O(log n) | binary search |
| T(n) = T(n/2) + O(n) | O(n) | quickselect (avg), median of medians |
| T(n) = 2T(n/2) + O(1) | O(n) | tree traversal |
| T(n) = 2T(n/2) + O(n) | O(n log n) | merge sort, quick sort (avg) |
| T(n) = 2T(n/2) + O(n^2) | O(n^2) | — |
| T(n) = T(n-1) + O(1) | O(n) | linear recursion, factorial |
| T(n) = T(n-1) + O(n) | O(n^2) | quick sort worst, selection sort |
| T(n) = 2T(n-1) + O(1) | O(2^n) | naive fib, Tower of Hanoi, subsets |
| T(n) = n * T(n-1) | O(n!) | permutations |
| T(n) = T(n-1) + T(n-2) | O(phi^n) ~ O(1.618^n) | naive fibonacci |
Master theorem, T(n) = aT(n/b) + O(n^d): compare d with log_b(a). d < log_b(a) -> O(n^(log_b a)); d = log_b(a) -> O(n^d log n); d > log_b(a) -> O(n^d).
(d) How to say it out loud#
| Term | Meaning (one line) |
|---|---|
| Amortized | average cost per op over a sequence; e.g. push is O(1) amortized though a single resize is O(n) |
| In-place | O(1) auxiliary space; mutates the input |
| Auxiliary space | extra memory beyond the input (what "space complexity" usually means in interviews) |
| Stable | equal keys keep their original relative order |
| Tight bound (Theta) | both upper and lower bound match; "O" alone is just an upper bound |
| Worst case vs average case | quick sort is O(n log n) average, O(n^2) worst |
| Best case | often O(n) for adaptive sorts (insertion, TimSort) on sorted input |
| Linearithmic | O(n log n) |
| Pseudo-polynomial | polynomial in the numeric VALUE of the input, not its bit length (knapsack O(nW)) |
| Overlapping subproblems | the same subproblem recurs -> memoize |
| Optimal substructure | optimal solution built from optimal sub-solutions -> DP / greedy |
| Greedy-choice property | a locally optimal choice is safe; prove with an exchange argument |
| Invariant | property that holds before and after every loop iteration (say it for two pointers, sliding window, binary search) |
| Monotonic | always non-decreasing or non-increasing; enables binary search on the answer |
| Online algorithm | processes input as it arrives (insertion sort, running median) |
| Divide and conquer | split, solve recursively, combine (merge sort) |
| Top-down vs bottom-up | memoized recursion vs iterative tabulation |
| Space-optimized / rolling array | keep only the previous row(s) of the DP table |
| Alpha(n) | inverse Ackermann; effectively constant (union-find) |
See also