Someone instrumented a function with an operation counter and handed you the numbers. Given counts, an array of [n, operations] samples, return the complexity class as a string.
- The answer is one of
"O(1)", "O(log n)", "O(n)", "O(n log n)", "O(n^2)" — check them in exactly that order - Their growth functions are
1, log2(n), n, n * log2(n), n * n - Scale a candidate
f to the first sample: c = counts[0][1] / f(counts[0][0]) - The candidate fits when every sample
[n, ops] satisfies Math.abs(c * f(n) - ops) <= 0.15 * ops — a 15% tolerance, so that real measurements with a bit of noise still classify - Return the first candidate that fits; the data is always clean enough that one does
counts has at least two samples and every n is at least 2