# Algorithmic complexity

Source: https://codewiki.com/foundations/algorithmic-complexity/

> - **what**: Algorithmic complexity describes how an algorithm's time or extra storage grows as its input grows, independent of one machine or benchmark.
> - **trap**: `O(n)` is a growth bound, not a duration, and `n` must name the input dimension that actually drives the work.
> - **fix**: Define the input size and cost model, derive time and space bounds for relevant cases, then measure representative limits before choosing an implementation.

## What it is and why it exists

Algorithmic complexity is a model of resource growth. It relates an input size such as the number of orders, graph vertices, or bytes to the work or additional storage an algorithm needs. The model usually focuses on behavior as the input becomes large, which is why it is called asymptotic notation.

Time complexity counts a chosen unit of work rather than seconds. That unit might be comparisons, hash-table operations, visited nodes, or bytes decoded. Space complexity counts memory that changes with input size, usually separating auxiliary workspace from storage already occupied by the input and required output.

The model answers a different question from a benchmark. A benchmark says how one implementation behaved on particular data, hardware, runtime, and load. Complexity explains why doubling input might leave work nearly unchanged, double it, or multiply it by four.

This distinction makes complexity durable. Processor speed and runtime optimizations can change constants, but they do not rescue an implementation whose operation count grows too quickly for the intended input. The analysis also exposes trade-offs, such as using a set with linear extra space to avoid a quadratic duplicate search.

You use complexity whenever a collection grows, a loop nests, a recursive call branches, or a service accepts user-controlled input. It helps with code review, capacity planning, API design, denial-of-service resistance, and selecting data structures. It does not prove correctness, latency, or safety by itself.

A useful complexity statement names its assumptions. “Lookup is expected `O(1)` for `n` entries under the hash-table contract” is actionable; “this is fast” is not. The statement should also say whether it describes worst-case, expected, amortized, or another case.

Complexity is one requirement among several. An implementation with a better bound can still be wrong, leak data, reorder results, or exceed a small fixed latency budget. Preserve the behavioral contract first, then compare resource growth among correct candidates.

Two implementations with the same asymptotic class can also scale differently in practice. One linear pass may allocate an object per item while another streams through contiguous memory. The shared `O(n)` label is the start of comparison, not its conclusion.

## How it works

### Define the input before counting

Start by choosing the input dimension. For a function that scans one array, `n` can be its length. For a graph, you often need both vertices `V` and edges `E`; collapsing them into one `n` hides whether the graph is sparse or dense.

Several independent inputs deserve several variables. Comparing every incoming product with every catalog product costs `O(nm)`, where `n` and `m` are the two collection sizes. Calling that `O(n²)` silently assumes they always grow together.

The numeric value of an input can differ from its representation size. Trial division up to an integer `x` performs work related to `√x`, but an integer stored in binary has about `log₂ x` bits. Cryptographic and numeric analyses therefore state whether size means value, digits, bits, rows, or bytes.

An input model can include structural parameters too. A tree's height, a string's encoded byte length, or the maximum number of neighbors per node may predict cost better than element count alone. Keep a parameter when product limits or hostile input can change it independently.

### Choose a cost model

Count operations whose cost is stable enough for the decision. A comparison-based search can count comparisons, while a parser may count bytes examined. Treating every library call as one step is unsafe when a call such as `includes()`, `sort()`, string concatenation, or serialization contains input-dependent work.

The model can deliberately abstract machine details. It normally treats array indexing and fixed-width arithmetic as constant time, subject to the language and data representation. If values can grow without bound, arithmetic on a thousand-bit integer is not the same operation as arithmetic on a machine word.

After selecting a unit, derive a function such as `3n + 7` comparisons. Asymptotic analysis groups functions by how they grow and drops constant factors and lower-order terms, so `3n + 7` is `O(n)`. The discarded terms still matter for small inputs and benchmarks; they simply do not change the growth class.

Peak resource use and cumulative work are different measurements. Allocating and releasing ten `n`-byte buffers uses `O(n)` peak auxiliary space but performs `O(n)` allocation work ten times. Name the resource being bounded so a memory claim is not mistaken for an allocation-rate claim.

### Read the common growth classes

The usual classes form an increasingly strict capacity ladder. Their names describe shapes, not promised elapsed times.

| Class | Typical source | Effect of doubling a large `n` |
| --- | --- | --- |
| `O(1)` | Direct lookup by index | Roughly unchanged |
| `O(log n)` | Repeatedly halve the remaining range | Adds roughly one step |
| `O(n)` | Visit every item once | Roughly twice the work |
| `O(n log n)` | Process every item across logarithmic levels | A little more than twice |
| `O(n²)` | Compare every pair | Roughly four times the work |
| `O(2ⁿ)` | Explore every subset choice | Squares when `n` doubles |

“Constant time” does not mean instant, and “linear” does not mean slow. An `O(1)` remote request can take longer than an in-memory `O(n)` scan of twenty values. Complexity becomes decisive when the changing input is large enough for growth to dominate constants.

Polynomial and exponential classes have very different ceilings. An exponential search can be practical for twenty choices and impossible for one hundred, while a quadratic pass may be acceptable under a hard cap of fifty rows. Translate the class into the actual input envelope before approving or rejecting it.

### State what the bound means

Big O gives an asymptotic upper bound: beyond some point, growth is no faster than a comparison function up to a constant factor. Big Omega gives a lower bound, and Big Theta gives a matching upper and lower bound. In casual engineering speech, people often say “Big O” when they intend a tight growth class, so ask whether the claim is only an upper bound.

A linear scan is `O(n)` in the worst case because it may inspect every item. Its best case is `O(1)` when the first item matches. An average or expected bound needs an input distribution, randomness assumption, or data-structure contract; it is not the arithmetic midpoint between best and worst cases.

Worst-case analysis supplies a ceiling and is especially useful for latency budgets or adversarial input. Expected analysis can better predict normal operation when its assumptions match production. Report both when the worst case is materially different and reachable.

Average-case claims should identify what is averaged. It could be all input permutations, observed production traffic, random hash seeds, or a sequence of operations. Those distributions are not interchangeable, and yesterday's traffic sample may not cover tomorrow's abuse pattern.

### Combine costs from code structure

Sequential phases add their costs. An `O(n)` validation followed by an `O(n log n)` sort costs `O(n + n log n)`, which simplifies to `O(n log n)`. Simplification does not authorize deleting validation; it only identifies which term dominates as `n` grows.

Nested work often multiplies. Two loops that each traverse all `n` items produce `n²` iterations, but a nested loop is not automatically quadratic. If two pointers only move forward across the whole run, the total can remain `O(n)` even though one loop appears inside another.

Work that repeatedly shrinks the problem by a constant factor is logarithmic. Binary search halves one sorted range per comparison, so the number of remaining halvings is proportional to `log n`. Sorting first is not free: one search after an `O(n log n)` sort is not an `O(log n)` end-to-end operation.

Recursive code is analyzed by how many subproblems it creates, how their sizes change, and what work occurs outside recursive calls. Memoization can collapse repeated subproblems, but then cache size becomes part of the space bound. A recursion depth of `n` also consumes `O(n)` stack space even when each frame does constant work.

Data-dependent loops can be counted with a sum instead of judging indentation. If iteration `i` examines `i` elements, total work is `1 + 2 + ... + n`, which is `Θ(n²)`. If each element is removed or advanced past at most once, the same-looking nesting may sum to `Θ(n)`.

### Count space and sequences of operations

Auxiliary space is memory used in addition to the input and required output. The pairwise duplicate check uses `O(1)` auxiliary space, while a set-based check stores up to `n` identifiers and uses `O(n)`. Output-sensitive algorithms may also report output space separately because returning `k` matches necessarily costs at least `O(k)` storage.

Some operations are occasionally expensive but cheap over a sequence. A geometrically growing array sometimes copies all existing elements during resize, yet `n` appends perform only linear total copying. Its append cost is therefore amortized `O(1)`, although one individual append can be `O(n)`.

Amortized and average-case analysis are not synonyms. Amortized analysis bounds the total cost of any relevant operation sequence and divides that cost across the sequence; it does not require a probability distribution. Average-case analysis depends on how inputs or operations are distributed.

Space analysis uses a lifetime boundary just as time analysis uses an operation boundary. A per-request set can be reclaimed after one request, while a process-wide memo table accumulates across requests. Both may hold `O(n)` entries for their own `n`, but only the second couples memory to the lifetime traffic cardinality.

## Examples

These examples count modeled operations instead of timing tiny programs. The numbers are reproducible and make growth visible, while later measurements still decide whether the constants and runtime behavior fit a real service.

Each counter is part of the example rather than a general profiler. It records the operation named by the surrounding analysis, so changing that unit would require changing both the instrumentation and the claim.

### Comparing growth shapes

The first program turns five complexity classes into rough operation budgets. Powers of two make the logarithmic column easy to inspect.

<!-- quick -->

```javascript
// file: growth_table.js
const estimates = [
  ["O(1)", () => 1],
  ["O(log n)", (n) => Math.ceil(Math.log2(n))],
  ["O(n)", (n) => n],
  ["O(n log n)", (n) => n * Math.ceil(Math.log2(n))],
  ["O(n^2)", (n) => n * n],
];

for (const inputSize of [8, 64, 512]) {
  const row = estimates
    .map(([label, steps]) => `${label}=${steps(inputSize)}`)
    .join(", ");
  console.log(`n=${inputSize}: ${row}`);
}
```

```text
n=8: O(1)=1, O(log n)=3, O(n)=8, O(n log n)=24, O(n^2)=64
n=64: O(1)=1, O(log n)=6, O(n)=64, O(n log n)=384, O(n^2)=4096
n=512: O(1)=1, O(log n)=9, O(n)=512, O(n log n)=4608, O(n^2)=262144
```


<!-- /quick -->

Increasing `n` by a factor of eight adds only three estimated logarithmic steps. The same change multiplies the quadratic estimate by sixty-four. These are deliberately simple functions, not predictions of nanoseconds.

`n = 0` also shows why domain definitions matter. `log₂ 0` is not a finite operation count, so a real contract needs a base case. Complexity notation describes growth after a threshold and does not replace validation at the boundary.

The table uses ceilings because an indivisible halving step cannot occur a fraction of a time. Another cost model could differ by a small constant while keeping the same logarithmic class.

### Removing a quadratic duplicate search

An order importer must reject duplicate identifiers. The first implementation compares every pair without allocating a collection; the second remembers identifiers in a set.

```javascript
// file: duplicate_orders.js
function findDuplicatePairwise(orderIds) {
  let operations = 0;
  for (let left = 0; left < orderIds.length; left += 1) {
    for (let right = left + 1; right < orderIds.length; right += 1) {
      operations += 1;
      if (orderIds[left] === orderIds[right]) {
        return { duplicate: orderIds[left], operations };
      }
    }
  }
  return { duplicate: null, operations };
}

function findDuplicateWithSet(orderIds) {
  const seen = new Set();
  let operations = 0;
  for (const orderId of orderIds) {
    operations += 1;
    if (seen.has(orderId)) return { duplicate: orderId, operations };
    seen.add(orderId);
  }
  return { duplicate: null, operations };
}

const orders = ["A-102", "B-205", "C-330", "D-404", "C-330"];
console.log("pairwise:", findDuplicatePairwise(orders));
console.log("set:", findDuplicateWithSet(orders));

for (const size of [10, 100]) {
  const unique = Array.from({ length: size }, (_, index) => `O-${index}`);
  console.log(`unique ${size}: pairwise=${findDuplicatePairwise(unique).operations}, set=${findDuplicateWithSet(unique).operations}`);
}
```

```text
pairwise: { duplicate: 'C-330', operations: 9 }
set: { duplicate: 'C-330', operations: 5 }
unique 10: pairwise=45, set=10
unique 100: pairwise=4950, set=100
```


With no duplicate, the pairwise version performs `n(n - 1) / 2` equality comparisons, so its worst-case time is `Θ(n²)`. The set version performs one membership check per identifier and has expected `Θ(n)` time under the set's hashing contract. It uses `Θ(n)` auxiliary space, while the pairwise version uses `Θ(1)`.

The observed counts are not directly comparable CPU instructions: a set operation does more work than one string equality check. At one hundred unique identifiers, however, the gap is already 4,950 modeled operations against 100. Benchmark both implementations near the expected crossover if memory is tight or inputs are always tiny.

An early duplicate improves both implementations' observed work but does not change their worst-case bounds. Keeping unique input in the test forces each implementation down the path that establishes those bounds.

### Seeing amortized append cost

This small buffer exposes the resizing that a dynamic array normally hides. Capacity doubles whenever an append has no free slot, so occasional pushes copy existing elements.

```javascript
// file: amortized_buffer.js
class OrderBuffer {
  #items = new Array(1);
  #size = 0;

  copiedSlots = 0;

  push(orderId) {
    if (this.#size === this.#items.length) {
      const grown = new Array(this.#items.length * 2);
      for (let index = 0; index < this.#size; index += 1) {
        grown[index] = this.#items[index];
        this.copiedSlots += 1;
      }
      this.#items = grown;
      console.log(`resize: capacity=${this.#items.length}, copied=${this.#size}`);
    }
    this.#items[this.#size] = orderId;
    this.#size += 1;
  }

  snapshot() {
    return this.#items.slice(0, this.#size);
  }
}

const buffer = new OrderBuffer();
for (let id = 1; id <= 8; id += 1) buffer.push(`O-${id}`);

console.log(`pushes=8, total copies=${buffer.copiedSlots}`);
console.log(buffer.snapshot().join(", "));
```

```text
resize: capacity=2, copied=1
resize: capacity=4, copied=2
resize: capacity=8, copied=4
pushes=8, total copies=7
O-1, O-2, O-3, O-4, O-5, O-6, O-7, O-8
```

The expensive pushes copy one, two, and four slots, for seven copies across eight appends. Continuing to capacity sixteen adds eight copies, and the geometric sum remains below twice the number of appends. That total-cost argument establishes amortized `O(1)` append.

Geometric growth is the important assumption. Increasing capacity by one slot would copy `1 + 2 + ... + (n - 1)` elements and make a sequence of appends `Θ(n²)`. The buffer also retains unused capacity, so the constant factor in its `O(n)` space use still affects memory planning.

The example implements its own buffer only to reveal the accounting. Production code should normally use the runtime's collection and rely on its documented behavior instead of replacing a mature implementation.

## Pitfalls

### Treating a bound as a stopwatch

> **Pitfall:** Saying an `O(n)` function takes “n milliseconds” mixes a growth class with a duration. Different operations, constants, runtimes, hardware, caches, and workloads can reverse results at practical sizes.

**Fix:** use complexity to eliminate growth that cannot fit the input envelope, then benchmark remaining candidates with representative data and report units, percentiles, environment, and variance. Keep the derived operation count beside the timing result so the measurement has an explanation.

### Choosing the wrong `n`

> **Pitfall:** Calling a two-input join `O(n²)` hides the case where one side is bounded and the other grows, while calling it `O(n)` may hide a second unbounded dimension. Using a numeric value instead of its encoded length can be exponentially misleading.

**Fix:** write a short input model before the bound, such as “`n` incoming rows, `m` catalog rows, and `b` bytes per key.” Preserve independent variables until product limits justify a relationship between them.

### Quoting an average without assumptions

> **Pitfall:** “Average `O(1)` lookup” is incomplete when keys can be adversarial, the hash function is unknown, or a latency objective forbids rare long pauses. Best-case behavior is not evidence for a normal-case distribution.

**Fix:** name the runtime or data-structure contract, key distribution, randomness, and collision behavior. Add a worst-case or percentile budget when one slow request matters, and test hostile as well as representative inputs.

### Hiding repeated linear work

> **Pitfall:** Generated and handwritten code often puts `includes()`, `find()`, array spread, front removal, serialization, or a database query inside a loop. The visible loop is linear, but its body may scan or copy growing data and make the whole path quadratic.

**Fix:** expand the cost of every call in the loop body and count how often it runs. Replace repeated membership scans with a suitable index or set, batch remote work, and add a doubling test that records operation counts or controlled timings.

### Buying speed with unbounded space

> **Pitfall:** A cache, memo table, or “seen” set can improve the time bound while retaining one entry per distinct input forever. Under a long-lived process or user-controlled keys, the optimization becomes a memory-exhaustion path.

**Fix:** include auxiliary space in the analysis and state who owns stored entries. Bound cardinality or lifetime, define eviction and cleanup, test high-uniqueness traffic, and keep a no-cache path when correctness must not depend on retained state.

### Optimizing the asymptotic label alone

> **Pitfall:** Rewriting clear bounded code solely to change `O(n)` into expected `O(1)` can add allocations, synchronization, invalidation bugs, and worse tail latency. The new bound may address an input size the product never reaches.

**Fix:** record the supported maximum, current operation counts, and measured crossover before changing the design. Accept the simpler implementation when it fits with margin, and add a regression threshold that tells maintainers when the trade-off should be revisited.

<!-- deep -->

## Turning a bound into an engineering decision

### Bounds are claims with quantifiers

Writing `T(n) = O(g(n))` claims that constants `c` and `n₀` exist such that `T(n) ≤ c g(n)` for every `n ≥ n₀`. The threshold permits small inputs to behave irregularly, while the constant permits implementations with the same shape to do different amounts of work. Big O alone does not claim that `g` is the smallest valid upper bound.

A product limit can technically make all accepted inputs bounded by one constant, but calling every operation `O(1)` under that cap destroys the model's value. Analyze growth in the natural variable, then state the enforced maximum separately. This preserves a useful comparison and a concrete operational guarantee.

For example, `3n + 7` is both `O(n)` and `O(n²)`, but only the linear description is tight. A useful review asks for `Θ(n)` when both upper and lower bounds match. A lower bound for one implementation is also different from a lower bound for the underlying problem; a slow implementation does not prove every solution must be slow.

### Input shape can dominate input count

Two inputs with the same `n` can take different paths. Early exits depend on match position, quicksort variants depend on pivot balance, graph traversal depends on both vertices and edges, and a hash table depends on collisions. Report the parameters or cases that select those paths instead of averaging away the distinction.

Adversarial inputs deserve explicit treatment at trust boundaries. A request body can force deep recursion, pathological matching, excessive hash collisions, or an enormous output even when ordinary fixtures are cheap. Complexity review is therefore part of abuse-case analysis, not only an optimization exercise.

Output size can impose a lower bound. If an endpoint must return `k` matching records, it needs at least `Ω(k)` time to emit them and usually `Ω(k)` bytes on the wire. Pagination may bound one response, but computing a total count or retaining a cursor can move work elsewhere rather than remove it.

Sparse and dense representations show why multiple parameters matter. An adjacency list occupies `Θ(V + E)` space, while a full matrix occupies `Θ(V²)` regardless of how many edges exist. Neither label is complete unless the graph density and operations required by the product are known.

### Constants and crossover points remain real

An asymptotically better implementation can lose for every input the product actually accepts. Building a set allocates memory and computes hashes; scanning a tiny array has a small, cache-friendly loop. The decision should state the supported input range and locate the crossover with a reproducible measurement.

Hardware and runtime behavior change constants in structured ways. Contiguous access benefits caches, allocation can trigger garbage collection, branch patterns affect processors, and vectorized library code can outperform a smaller operation count written in user code. These facts refine the model; they do not invalidate growth analysis.

Remote calls need their own dimension and budget. Turning `n` local operations into `n` database queries may still be written `O(n)`, but latency and service load can become unacceptable. Count round trips, bytes, concurrency, and downstream work alongside local CPU operations.

Concurrency changes elapsed time without necessarily reducing total work. Running `n` independent requests in parallel may shorten the critical path while preserving `Θ(n)` downstream operations and increasing peak connections or memory. Report work, span, and resource limits separately when parallelism drives the design.

### Validate the model by doubling

A doubling test runs controlled inputs of size `n`, `2n`, `4n`, and larger while keeping shape and environment stable. Ratios near two suggest linear growth, near four suggest quadratic growth, and a slowly increasing ratio can fit `n log n`. This is evidence about an implementation over the measured range, not a mathematical proof.

Instrumented counts often diagnose more cleanly than short timings. Count comparisons, visited nodes, allocations, copied bytes, queries, and retained entries, then use a benchmark for constants and system effects. If the count disagrees with the derivation, inspect hidden work or a mistaken input model before tuning.

Measurement needs a written protocol. Pin the runtime and dependency versions, generate data deterministically, separate warm-up from steady state where relevant, repeat enough samples, and report distributions rather than a single fastest run. Keep correctness assertions active so a fast implementation cannot win by skipping work.

Do not fit a growth class from two noisy points. Use enough sizes to move past fixed setup costs, inspect operation counts when possible, and plot or tabulate ratios. Stop increasing input before a test can exhaust shared memory or overload an external dependency.

### Turn limits into a budget

Start from the largest supported input rather than from notation alone. Substitute that value into a conservative operation and memory estimate, account for concurrent requests, and compare the result with CPU, latency, and memory budgets. If one request can consume the whole budget, add admission limits even when typical inputs are small.

The final decision should record the chosen implementation, input envelope, bound and case, assumptions, measured crossover, and fallback when limits are exceeded. This record makes later changes reviewable. When data shape or service limits change, rerun the derivation and measurement instead of repeating the old label.

Limits must fail predictably. Reject an oversized request before expensive parsing where possible, paginate output, bound recursion or queues, and attach timeouts to remote work. A documented complexity bound is most useful when runtime guards enforce the input assumptions behind it.

<!-- /deep -->

[Checkpoint: foundations/algorithmic-complexity](https://codewiki.com/foundations/algorithmic-complexity/#checkpoint)

## Further reading

- [NIST Dictionary of Algorithms and Data Structures: Big-O notation](https://xlinux.nist.gov/dads/HTML/bigOnotation.html)
- [MIT OpenCourseWare: Introduction to Algorithms lecture notes](https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-fall-2011/pages/lecture-notes/)
- [MDN Web Docs: `Set`](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Set)
- [Python Wiki: operation complexity of built-in containers](https://wiki.python.org/moin/TimeComplexity)
- [Princeton Algorithms: analysis of algorithms](https://algs4.cs.princeton.edu/14analysis/)