Algorithmic complexity is a performance property: how an operation's cost grows with the size of its input. A routine that is accidentally $O(n^2)$ where $O(n \log n)$ was intended is invisible at test sizes ($n = 10$) and dominates at production scale ($n = 10^6$).

The measuring methods answer the average case: load and stress testing under a representative profile, microbenchmarking of a function, profiling of a realistic dataset. The methods here target the growth curve and the worst case, which an average-case benchmark never provokes. When an attacker can choose the input that forces the worst case, the same cost becomes a denial of service, a security concern rather than a performance one.

What it catches

Cost that grows faster than its input:

• Accidentally-quadratic hot paths. A parser, serializer, or membership loop that degrades to $O(n^2)$. The same accidental growth can hide in a resource count rather than CPU time, as in the database N+1 query.
• Worst-case denial of service. An attacker-chosen input that forces the pathological path. Its regex form (ReDoS) is caught before it runs by a static linter; the general case needs complexity fuzzing.

Approaches and tools

Empirical big-O regression

Run the operation across a sweep of input sizes and fail the build when the growth curve bends superlinear: roughly, when $t(2n)/t(n)$ trends toward 4× rather than ~2×. That is an ordinary microbenchmarking or load and stress testing gate applied across sizes, not a separate tool. No reliable static detector for the "accidentally quadratic" case exists.

A common special case needs no size sweep at all: the database N+1 query. One query is issued per row instead of one for the whole set, so the query count grows with the row count where it should stay constant. Query count is a cleaner signal than wall-clock time here, and dedicated tools assert on it directly: Bullet flags N+1 queries and unused eager loading in a Rails app during development and test runs; in Java, QuickPerf's @ExpectSelect(n) annotation fails a JPA/Hibernate test when the query count exceeds a bound; Django ships assertNumQueries(n) as a built-in, and the nplusone package surfaces the lazy loads at runtime.

Complexity fuzzing

Where the growth-curve gate requires the sizes to be named in advance, complexity fuzzing searches for the pathological input a reviewer will not imagine. It evolves inputs to maximize execution cost: SlowFuzz (Petsios et al. 2017)¹ and the later, AFL-based PerfFuzz (Lemieux et al. 2018)² are the two research tools. It is a specialization of fuzzing: where an ordinary fuzzer searches for an input that crashes, a complexity fuzzer searches for one that is slow. Aimed at parsers, serializers, and hash-table code on a security boundary, it is also the most direct answer to the worst-case denial-of-service question.

When to use, when not

Use:

• To catch an N+1 query on any request that loops over a collection and touches the database or an external service. A query-count assertion is cheap and pins the regression precisely.
• To harden code that parses, deserializes, or hashes attacker-controlled input, where the worst case sits on a security boundary. Complexity fuzzing searches for the pathological input directly.
• To gate a hot library function with an empirical big-O sweep when its inputs grow unboundedly in production.

Don't:

• For code whose input is bounded and small. The growth curve is irrelevant and a big-O sweep is noise.
• As a proof of safety. A clean complexity fuzz run found no blow-up in the budget it ran, nothing more.

Evidence

• Search finds pathological inputs automatically. SlowFuzz drove algorithmic-complexity blow-ups in real-world libraries by evolutionary search over the input (Petsios et al. 2017)¹; PerfFuzz, maximizing each program location's execution count, exercised the most-frequently executed branch 5–69× more often than SlowFuzz on four C libraries (Lemieux et al. 2018)².

Related

Performance

These aren't competing choices — they answer different performance questions, at different scopes. Microbenchmarking measures the cost of one small unit in isolation. Profiling explains where time or memory goes in a real workload. Load and stress testing drives the whole system under traffic to find where it degrades. You reach for whichever fits the question.

Bounding a program's cost

All three ask how much a computation costs, and meet the same undecidable core (the halting problem) at different guarantee levels. Termination analysis proves the qualitative floor: does the program halt at all, over every input. Worst-case execution-time analysis assumes it halts and proves a sound upper bound on running time for the modeled hardware. Algorithmic complexity testing trades proof for search: it hunts an input that drives cost past its expected growth, witnessing a lower bound on how bad the worst case gets.

Termination is the precondition, since a runtime that might be infinite has no bound to compute. WCET and complexity testing then bracket the same worst case from opposite sides: WCET over-approximates (sound, never optimistic, sometimes pessimistic), while complexity testing under-approximates (a blow-up it finds is real, but finding none proves nothing). The two sound static methods and the one empirical search are the formal and the testing answers to a single question about resource use.

Classification

• Quality dimensions: Performance, Security.
• Area: Code whose cost grows with input size: parsers, serializers, hash tables, database access, hot loops; scalability review and worst-case (denial-of-service) hardening.
• Guarantee: Empirical: a found input proves a blow-up exists; not finding one proves nothing about the worst case.

Referenced by

• Performance · Quality dimensions
• Security · Quality dimensions
• Deep static analysis · Methods
• Fuzzing · Methods
• Search-based software testing (SBST) · Methods

References

---

1. Petsios, Theofilos, Jason Zhao, Angelos D. Keromytis, and Suman Jana. 2017. "SlowFuzz: Automated Domain-Independent Detection of Algorithmic Complexity Vulnerabilities." Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security (CCS '17), 2155–68. https://doi.org/10.1145/3133956.3134073. ↩↩

2. Lemieux, Caroline, Rohan Padhye, Koushik Sen, and Dawn Song. 2018. "PerfFuzz: Automatically Generating Pathological Inputs." Proceedings of the 27th ACM SIGSOFT International Symposium on Software Testing and Analysis (ISSTA 2018), 254–65. https://doi.org/10.1145/3213846.3213874. ↩↩