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.
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.
How work grows with input size
Select at least one complexity class to draw the chart.
| Complexity | n | Modeled 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.
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.
Binary search
Count midpoint comparisons while a sorted random-access range is repeatedly halved.
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.
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.
Dynamic-array append
Compare a spare-capacity write, a resize event, and the aggregate cost of many appends.
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
- Count the fixed reads or pointer writes.
- The count remains bounded as n grows.
- 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
- After k halvings, n / 2^k <= 1.
- Therefore 2^k >= n.
- 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
- A composite n has factors a * b = n.
- At least one factor is no larger than sqrt(n).
- 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
- Count at most one visit per item.
- n items produce n bounded visits.
- 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
- Halving creates log2(n) levels.
- All nodes at one level process n items total.
- 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
- The outer loop runs n times.
- The inner work is proportional to n.
- 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
- Each loop contributes a factor of n.
- Nested loops multiply their counts.
- 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
- Level 0 has one call.
- Each level can double the calls.
- 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
- There are n choices first.
- Then n-1, n-2, and so on.
- 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
- Count n visits in the first pass.
- Count m visits in the second.
- 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
- The outer input contributes n iterations.
- Each scans m inner items.
- 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
- Visit each of V vertices.
- Inspect the adjacency entries totaling E (or 2E undirected).
- 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
- Process V vertex removals and up to E relaxations.
- Heap updates cost O(log V).
- 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
- Navigate the balanced index in logarithmic height.
- Emit k matching results.
- 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
- Most appends write one item.
- Resize copies form a geometric series: 1 + 2 + 4 + ... < 2n.
- 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.