Counting Operations: How Work Grows
Try it: Counting Operations: How Work Grows
Computational complexity as a count of operations: run a function once and count every basic operation (each costing a constant c on an abstract machine), then run it for a whole sequence of input sizes and compare how the count changes with growth functions 1, log n, n and n^2, which is what an O(f) statement describes.
How it works
- Stage 1, one fixed task: run the function at one size and count every operation on the lines marked "counted" (a comparison, a division, one feature of a distance).
- The abstract machine charges the same constant c microseconds per operation, so running time = c x count, whatever the code looks like.
- Stage 2, a sequence of tasks: run the same function again for every size 1..N and plot the count against the size.
- Doubling test: for f = 1, log n, n, n^2 in turn, compare count/f at N/2 and at N; the first f for which that ratio stops growing is the growth class O(f).
- The ratio settles to a constant (1/2 for the pairs loop, d + 1 for nearest-neighbour search): the constant, lower-order terms and c rescale the curve but do not change its growth.
Default run (54 steps): Stage 1, one fixed task: run equal_pairs at n = 6 and count every operation on a line marked "counted". … count(n) <= 0.4844 x n^2 for every n from 2 to 32, and the ratio settles near 0.4844. That constant, the lower-order terms and c only rescale the curve, so the growth class is O(n^2).
Simplified: Five small, fixed functions with their counted lines chosen in advance (one comparison, division or feature step = one operation); their counts do not depend on the values, so the statement holds for every input of a size (the learning-theory definition also quantifies over every distribution D). The growth class is read from a finite sweep (N up to 64) with a doubling test and a 10 % tolerance; a real O(f) claim is about all sufficiently large sizes and needs a proof.
Loading the simulation…