← Trace Lab

Operation Complexity Lab

Count the work.
Then name the growth.

Big O is not a stopwatch result. Choose the input, implementation, case, and primitive operation; count deterministic work; then simplify how that count grows.

15 required growth families
9 comparable one-input curves
7 operation cases with derivations

Measurement contract

Operation count ≠ wall-clock time

Complexity compares growth under a model. Benchmarks measure one real environment.

What this lab measures

Deterministic primitive work

  • Comparisons, reads, writes, copies, calls, and other named operations
  • The exact input variables and implementation variant
  • The selected best, average, worst, expected, or amortized case
  • Auxiliary space separately from returned output

What Big O does not promise

A duration on a particular machine

  • CPU speed, cache behavior, runtime warm-up, allocation, and compiler effects
  • Equal speed for two implementations in the same growth family
  • A useful claim when the counted operation or assumptions stay unnamed
  • That constants and lower-order terms never matter at real input sizes

ReplayCS plots representative formulas so their shapes can be compared. A curve is not a benchmark and its vertical value is not seconds. Change the implementation, representation, case, or assumptions and the valid complexity claim may change too.

Interactive growth chart

See when growth overwhelms constants

Toggle families and input size. Linear and logarithmic scales answer different visual questions, while capped values keep explosive families safe to inspect.

Operation count, not elapsed time

How work grows with input size

Linear scale
Chart scale
Complexity classes to compare

Select at least one complexity class to draw the chart.

Representative growth values at input size 2
ComplexitynModeled operations
No classes selected.

Cases, counts, and space

Ground the notation in real operations

An algorithm name alone is not an analysis. Inspect the concrete input, variant, selected case, exact count formula, auxiliary space, assumptions, and derivation together.

01

Live trace connected

Binary search: one algorithm, different cases

The first midpoint is constant work in the best case; repeated halving is logarithmic in typical and worst cases. Recursion changes auxiliary space even when time stays the same.

Operation Complexity Explorer · model v1

Binary search

Count midpoint comparisons while a sorted random-access range is repeatedly halved.

best case O(1) O(1) auxiliary space
What this operation does

Target at the first midpoint

The first midpoint already contains the target.

Selected case
best
Time
O(1)
Auxiliary space
O(1)
Counting model / bound
1 midpoint comparison

Assumptions behind this result

  • Input is sorted.
  • Indexed access is constant time.

Change an assumption and the complexity may change too.

02

Sequence accounting

Dynamic-array append: worst event vs amortized cost

A resize copies n elements, so that individual append is linear. Geometric capacity growth keeps the total cost of a long sequence linear, making the per-append amortized cost constant.

Operation Complexity Explorer · model v1

Dynamic-array append

Compare a spare-capacity write, a resize event, and the aggregate cost of many appends.

best case O(1) O(1) auxiliary space
What this operation does

Spare capacity

Write the new value into the next unused slot and increment size.

Selected case
best
Time
O(1)
Auxiliary space
O(1)
Counting model / bound
1 element write

Assumptions behind this result

  • The backing allocation has an unused slot.
  • Capacity bookkeeping is constant time.

Change an assumption and the complexity may change too.

Complete reference

All 15 families, with the assumptions attached

Open any family for its real scenarios and derivation. Similar-looking formulas remain separate when their variables describe different parts of the input.

One growing input

Recognize the shape of n

These families compare work as one primary input grows. The formula names the modeled operation count, not elapsed milliseconds.

O(1) Constant work The counted operation does not grow with the input size.
Representative count
c
Example input
n = 16

Real scenarios

  • Array index access
  • Stack peek
  • Linked-list insertion at head

Assumptions

  • The target position or pointer is already known.
  • This describes operation count, not wall-clock time.

Derivation

  1. Count the fixed reads or pointer writes.
  2. The count remains bounded as n grows.
  3. Drop the constant coefficient.
O(log n) Halving work Each operation discards a constant fraction of the remaining input.
Representative count
ceil(log2 n)
Example input
n = 16

Real scenarios

  • Binary search
  • Balanced BST search
  • Heap-height operation

Assumptions

  • Binary search input is sorted.
  • Tree height remains logarithmic when balance is maintained.

Derivation

  1. After k halvings, n / 2^k <= 1.
  2. Therefore 2^k >= n.
  3. Solve for k: k >= log2 n.
O(sqrt n) Square-root boundary Work stops once a paired factor would repeat.
Representative count
ceil(sqrt n)
Example input
n = 49

Real scenarios

  • Trial-division primality checking

Assumptions

  • Testing divisors only through sqrt(n) is sufficient for primality.

Derivation

  1. A composite n has factors a * b = n.
  2. At least one factor is no larger than sqrt(n).
  3. Test only that bounded prefix.
O(n) One pass Each input item may be visited once.
Representative count
n
Example input
n = 16

Real scenarios

  • Linear search
  • Array traversal
  • Linked-list search

Assumptions

  • The worst case reaches every item.
  • Per-item work is bounded.

Derivation

  1. Count at most one visit per item.
  2. n items produce n bounded visits.
  3. The dominant term is n.
O(n log n) Logarithmic levels, linear work each Divide-and-conquer creates logarithmic levels with linear total work per level.
Representative count
ceil(n * log2 n)
Example input
n = 16

Real scenarios

  • Merge sort
  • Heap sort
  • Balanced divide and conquer

Assumptions

  • Subproblems remain balanced.
  • Each level processes all n items in bounded work.

Derivation

  1. Halving creates log2(n) levels.
  2. All nodes at one level process n items total.
  3. Multiply n by the number of levels.
O(n^2) All pairs For each input item, work may scan a linear-sized set.
Representative count
n * n
Example input
n = 12

Real scenarios

  • Bubble sort worst case
  • Selection-sort comparisons
  • All-pairs comparison

Assumptions

  • Both loop bounds grow with the same n.
  • Early exit does not shorten the selected case.

Derivation

  1. The outer loop runs n times.
  2. The inner work is proportional to n.
  3. Nested work multiplies to n^2.
O(n^3) Three-dimensional work Three input-dependent nested dimensions multiply.
Representative count
n * n * n
Example input
n = 8

Real scenarios

  • Naive square-matrix multiplication
  • Triple nested loop

Assumptions

  • All three dimensions use n.
  • The innermost work is bounded.

Derivation

  1. Each loop contributes a factor of n.
  2. Nested loops multiply their counts.
  3. n * n * n = n^3.
O(2^n) Binary branching Each decision can create two recursive branches.
Representative count
2^n
Example input
n = 12

Real scenarios

  • Subset generation
  • Naive recursive Fibonacci
  • Include/exclude recursion

Assumptions

  • Both branches continue through depth n.
  • Repeated subproblems are not memoized.

Derivation

  1. Level 0 has one call.
  2. Each level can double the calls.
  3. Depth n therefore has about 2^n nodes.
O(n!) Every ordering The algorithm explores every permutation of n choices.
Representative count
n!
Example input
n = 10

Real scenarios

  • Permutation generation
  • Brute-force route ordering

Assumptions

  • Equivalent orderings are not pruned.
  • Every complete permutation is produced or checked.

Derivation

  1. There are n choices first.
  2. Then n-1, n-2, and so on.
  3. Multiply the choices: n!.

Several independent variables

Keep different dimensions separate

Collections, graphs, and returned results do not always grow together. Preserve n, m, V, E, and k until an assumption relates them.

O(n + m) Two consecutive inputs Independent passes add instead of multiply.
Representative count
n + m
Example input
n = 12 · m = 8

Real scenarios

  • Scan two collections
  • Expected hash-join build plus probe

Assumptions

  • The passes are consecutive.
  • Hash operations are expected constant time for the join model.

Derivation

  1. Count n visits in the first pass.
  2. Count m visits in the second.
  3. Consecutive work adds to n + m.
O(nm) Cross-product work Each item from one input is paired with every item from another.
Representative count
n * m
Example input
n = 12 · m = 8

Real scenarios

  • Nested-loop join
  • Compare every row in two relations

Assumptions

  • There is no index or early termination.
  • The two input sizes may differ.

Derivation

  1. The outer input contributes n iterations.
  2. Each scans m inner items.
  3. Nested work multiplies to nm.
O(V + E) Graph traversal Adjacency-list traversal processes vertices and their stored edges.
Representative count
V + E
Example input
n = 8 · vertices = 8 · edges = 12

Real scenarios

  • BFS with an adjacency list
  • DFS with an adjacency list

Assumptions

  • The graph uses adjacency lists.
  • Each vertex and stored edge is processed a bounded number of times.

Derivation

  1. Visit each of V vertices.
  2. Inspect the adjacency entries totaling E (or 2E undirected).
  3. Drop the constant and add V + E.
O((V + E) log V) Graph work with a heap Vertex and edge events can trigger logarithmic priority-queue work.
Representative count
(V + E) * log2 V
Example input
n = 8 · vertices = 8 · edges = 12

Real scenarios

  • Dijkstra with adjacency lists and a binary heap

Assumptions

  • Non-negative edge weights.
  • A binary heap implements the priority queue.
  • The graph uses adjacency lists.

Derivation

  1. Process V vertex removals and up to E relaxations.
  2. Heap updates cost O(log V).
  3. Multiply the event bound by the heap cost.
O(log n + k) Lookup plus output Finding the range and returning its results both count.
Representative count
log2 n + k
Example input
n = 1024 · outputSize = 12

Real scenarios

  • B-tree indexed range query

Assumptions

  • The index remains balanced.
  • k is the number of returned records.
  • Storage and cache effects are abstracted.

Derivation

  1. Navigate the balanced index in logarithmic height.
  2. Emit k matching results.
  3. Add lookup and output costs.

Cost across a sequence

Amortized is not average-case

Amortized analysis distributes a guaranteed aggregate cost across operations; it does not assume a probability distribution over inputs.

Amortized O(1) Occasional expensive resize Rare O(n) resize events spread across many constant writes.
Representative count
(total cost across appends) / append count
Example input
n = 16

Real scenarios

  • Dynamic-array append with geometric capacity growth

Assumptions

  • Capacity grows geometrically, commonly by doubling.
  • The claim covers a sequence, not one resize event.

Derivation

  1. Most appends write one item.
  2. Resize copies form a geometric series: 1 + 2 + 4 + ... < 2n.
  3. Total work is O(n), so average per append is O(1).

A defensible complexity claim

Say what grows, what you counted, and why.

“The worst-case iterative binary search performs logarithmically many midpoint comparisons on a sorted random-access sequence” is useful. “Binary search is fast” is not an analysis.

Open the full Binary Search trace →