Complexity

Complexity#

The operator’s analysis pipelines work on collections that scale from a handful of indicators to millions of log lines, packet captures, or social-graph edges. Algorithmic complexity is how an algorithm’s resource use grows with input size, and it decides whether a triage script that handled yesterday’s haul finishes today’s before the brief is due. Time complexity is the usual focus; space complexity matters when the operator’s box has bounded memory or the analysis runs on a constrained target.

Big-O, Big-Theta, Big-Omega#

The three asymptotic notations. Big-O is the loose upper bound most engineers use as shorthand for “growth rate”; Big-Theta is the tight bound that says “no faster, no slower”; Big-Omega is the lower bound. Mathematicians distinguish; most engineers say “Big-O” for all three.

  • Big-O (O(f)), upper bound. “Grows no faster than f.”

  • Big-Theta (Θ(f)), tight bound. “Grows at the same rate as f.”

  • Big-Omega (Ω(f)), lower bound. “Grows at least as fast as f.”

In practice “Big-O” is used loosely for the tight bound; the math audience is more careful.

Common Growth Rates#

The growth rates engineers should recognize on sight, sorted from slowest-growing to fastest. Knowing where each algorithm sits is half of being able to predict whether code will scale without running benchmarks.

Notation

Name

Examples

O(1)

Constant

Hash table lookup (avg), array index

O(log n)

Logarithmic

Binary search, balanced tree operations

O(n)

Linear

One pass over n items

O(n log n)

Linearithmic

Mergesort, heapsort, optimal comparison sorting bound

O(n²)

Quadratic

Nested loops, insertion sort, naive matrix add

O(n³)

Cubic

Naive matrix multiply, Floyd-Warshall

O(2ⁿ)

Exponential

Brute-force subset / SAT, recursive Fibonacci

O(n!)

Factorial

Brute-force traveling salesman, generate all permutations

Best, Average, Worst Case#

The same algorithm has different complexities for different inputs. Pick by the case that matters: average for the typical workload, worst for critical paths under adversarial input (security, real-time systems, cost-bounded SaaS).

Algorithm

Best

Average

Worst

Quicksort

Θ(n log n)

Θ(n log n)

Θ(n²)

Mergesort

Θ(n log n)

Θ(n log n)

Θ(n log n)

Insertion sort

Θ(n)

Θ(n²)

Θ(n²)

Hash lookup

O(1)

O(1)

O(n) (collisions)

Binary search

O(1)

O(log n)

O(log n)

Pick by the case that matters: average for the typical workload, worst for critical paths under adversarial input.

Amortized Analysis#

The average cost over a sequence of operations, even if individual ones are expensive. Amortized analysis is what justifies “this is O(1)” claims about hash inserts and dynamic array pushes; the occasional expensive resize gets distributed over the cheap operations that follow.

  • Dynamic array push, O(n) to resize, but amortized O(1) because resizes are rare and double the capacity each time.

  • Hash table insert, amortized O(1) despite occasional O(n) rehashes.

  • Union-find with path compression, amortized O(α(n)) per operation, where α is the inverse Ackermann (effectively constant).

Space Complexity#

How much memory the algorithm uses, beyond the input. Most algorithm decisions involve a time-space trade; you can use more memory to go faster (memoization, lookup tables) or use less memory to fit a constrained system (streaming algorithms, in-place operations).

  • In-place, O(1) extra space (heapsort).

  • Linear extra space, mergesort, BFS / DFS over graphs.

  • Recursion stack counts; deep recursion uses O(depth) space.

Trade time for space (memoization, lookup tables) and vice versa (streaming algorithms, in-place operations).

Asymptotic vs. Practical#

Big-O ignores constants and lower-order terms. In practice, those constants and terms can dominate; a textbook-better algorithm can be measurably worse than a textbook-worse one if the constant factor is large or the cache behavior is bad. The asymptotic story is the first answer, not the only one.

  • O(n²) with a tiny constant can beat O(n log n) for small n. Insertion sort beats mergesort below ~30 elements.

  • Cache effects dominate when n fits in cache; an O(n) algorithm with bad cache behavior can lose to O(n log n) with sequential access.

  • Branch prediction, SIMD, and hardware prefetching matter at the level where Big-O ignores them.

The asymptotic story is the first answer, not the only one.

P, NP, NP-Hard, NP-Complete#

The classic complexity-class hierarchy from theoretical CS. Most operators don’t deal with these directly, but recognizing “this problem is NP-hard” is a useful signal; it tells you to reach for heuristics, approximations, or constraint solvers rather than exact algorithms.

  • P, decidable in polynomial time.

  • NP, “Non-deterministic Polynomial”; verifiable in polynomial time given a candidate solution.

  • NP-hard, at least as hard as the hardest NP problem.

  • NP-complete, in NP and NP-hard.

Famous NP-complete problems: Traveling Salesman (decision), SAT, Subset Sum, Graph Coloring, Knapsack (decision), Vertex Cover.

Whether P = NP is one of the most famous open problems. Most people in the field bet “no”, but it’s unproven.

Practical Heuristics#

The lookup table for “what complexity can I afford given my input size?” Each row assumes a ~1-second budget on a modern machine and roughly modern language overhead; knowing these ceilings helps you skip over algorithm choices that obviously won’t scale before writing any code.

  • If n ≤ 30: O(2ⁿ) works.

  • If n ≤ 100: O(n³) works.

  • If n ≤ 10⁴: O(n²) works.

  • If n ≤ 10⁶: O(n log n) works.

  • If n ≤ 10⁸: O(n) works (barely; tight loops, cache-aware).

These assume a ~1-second budget on a modern machine and roughly modern language overhead.

Profiling#

Always profile before optimizing. The most expensive line of code in any program is usually not the one a developer expects, and the best O(n²) code has often been beaten by an O(n log n) rewrite, while the best micro-optimization rarely matters at all.

  • Identify the hot path, the code that runs most.

  • Measure, a wall-clock measurement beats a Big-O argument every time.

  • Optimize the algorithm before the implementation.

The best O(n²) code has often been beaten by an O(n log n) rewrite; the best micro-optimization rarely matters at all.

Contents