·6 сценариев
topologyconceptsPublic
Big-O Cheatsheet for System Design
Big-O Cheatsheet for System Design — interactive concept page that visualizes complexity classes (O(1), O(log n), O(n), O(n log n), O(n²), O(2^n)) through node load sizes and capacity caps. Compares HashMap vs sorted array vs linked list lookup, B-tree vs LSM with Bloom filter, and brute-force kNN vs HNSW vs IVF+PQ. Includes 4 scenarios: lookup comparison at N=1B, sort comparison (mergesort vs bubble), disk indices (B-tree vs LSM+Bloom), and ANN with exponential warning. ADR explains when NOT to optimize complexity (small N, IO-bound, cache locality, rare execution).
Key · @kuzminykh_igor_b3550a9b0 звёзд
1 просмотр
только что · последнее обновление
Big-O cheat sheet
Asymptotic notation describes how a chosen resource grows with named input variables under a stated computation model.
Notation
- (f(n) in O(g(n))): an asymptotic upper bound.
- (f(n) in Omega(g(n))): an asymptotic lower bound.
- (f(n) in Theta(g(n))): both bounds hold, so the growth rate is tight.
"Big-O means worst case" is false. Worst, best, expected, and amortized describe which cost is analyzed; (O), (Omega), and (Theta) describe the bound.
Always state the contract
A useful complexity claim names:
- input variables such as (N), (V), (E), output size, key length, or dimensions;
- the operation and preconditions;
- worst/expected/amortized case;
- the resource: CPU operations, comparisons, memory, network bytes, or block I/O;
- the computation and adversary model;
- included preprocessing, build, and update work.
Common examples
| Operation | Defensible claim | Essential assumptions |
|---|---|---|
| Array scan | (Theta(N)) worst case | examining all elements may be necessary |
| Binary search | (Theta(log N)) worst-case comparisons | sorted random-access sequence |
| Comparison sort | (O(Nlog N)); comparison lower bound (Omega(Nlog N)) | comparison model |
| Hash lookup | expected (O(1)), worst (O(N)) | suitable hashing and controlled load |
| BFS/DFS | (Theta(V+E)) | adjacency-list representation |
| B-tree lookup | (O(log_B N)) node/block reads | fanout (B), balanced tree |
Amortized analysis is not average-case analysis. Dynamic-array/table resizing can have amortized constant update cost across every operation sequence even without a probability distribution.
System-design traps
Network calls, serialization, queueing, output size, skew, cache misses, and retries often dominate the textbook operation count. A database index lookup can be logarithmic in tree height but still return (K) rows and perform (O(K)) output work.
"Nearest-neighbor search is (O(log N))" is not a universal fact. Exact and approximate methods have dataset-, dimension-, parameter-, quality-, and index-specific trade-offs. Publish measured recall, latency distribution, memory, build time, and update cost.
Diagram scenarios
The animation covers bound notation, binary-search preconditions, expected versus worst-case hashing, amortized resizing, external-memory B-trees, and algorithm-specific graph/ANN claims.
Related concept
[CONCEPT]probabilistic-data-structuresInteractive scenarios
Комментарии · 0
Комментариев пока нет. Будьте первым.
Калькулятор ёмкости
Введите числа или выберите пресет