Growth rate
–
Candidates · average fit error
Measurements table
| n | measured | best fit |
|---|
How it works
- Run it at growing sizes. Your function runs in a Web Worker (a background thread) at n = 16, 32, 64, … until one call takes over a second. Fast calls are timed in batches because browser clocks only tick every ~0.1 ms.
- Fit each candidate. For every growth rate f(n) (1, log n, n, n log n, n², n³, bⁿ) it finds the best
time ≈ a·f(n) + b. Here a is the cost of one step and b is fixed overhead. - Pick the best fit. The candidate with the smallest relative error wins. If a simpler one fits almost as well, the simpler one wins.
These are real timings, so they're noisy. Garbage collection, CPU caches and the JavaScript JIT all shift the numbers, and O(n) vs O(n log n) is hard to tell apart. Treat the result as evidence, not proof. The proof is still reasoning about the code.