Elasticsearch query complexity: Elasticsearch
documents the complexity of its query types. A term query
is O(log n). A wildcard query is O(n) or worse depending on
the pattern. A developer who replaces a term query with a
wildcard query in a hot search path has changed the
system’s complexity class — which becomes visible when the index grows
from 1 million to 100 million documents.
Python’s sort: Python’s Timsort is O(n log n) worst case and O(n) best case on nearly-sorted data. The best-case behavior is intentional — real datasets are often partially sorted. Knowing this, Python developers use Timsort on partially-sorted inputs for O(n) performance without changing the algorithm. Understanding Big-O lets you reason about when these optimizations apply.
DNS TTL and cache invalidation: A DNS resolver that checks all cached entries on every request has O(n) lookup complexity where n is the number of cached entries. Resolvers that use hash tables have O(1) average lookup. The difference is invisible at 100 cached entries. At 10 million cached entries (a large anycast resolver), the O(n) design fails. Real DNS resolvers are designed as hash tables from the ground up because the scale requirement was known in advance.
Concept: Big-O notation — formal language for naming algorithmic growth rates
Thread: T12 (Tradeoffs) — Big-O is the vocabulary for naming complexity tradeoffs; every algorithm choice is a statement about growth rates
Core Idea: O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ). At n=10⁹, these differ by astronomical factors.
Tradeoff: AT9 — Big-O hides constants; an O(n log n) algorithm with large constants can be slower than O(n²) for all practical n values
Failure Mode: FM3 — treating O(n log n) as O(n) at n=10⁹ causes 30x resource overrun; treating O(n²) as acceptable at large n causes system failure
Signal: When “works fine in testing, fails in production”, the algorithm’s complexity class was not evaluated against production-scale n
Maps to: Reference Book, Framework 12 (Tradeoffs)