Bender - Episode 3 – CodinGame solution in Python
Divide every measured time t by each candidate function f(n) (1, log n, n, n log n, n², n² log n, n³, 2ⁿ). If the data really grows like f, the ratios t/f(n) are almost constant, so print the candidate whose ratios have the smallest coefficient of variation (variance divided by the squared mean).
The problem
You receive a list of measurements of some program: for each one, a data size n and the time it took to run. Your job is to guess its asymptotic complexity and print exactly one of O(1), O(log n), O(n), O(n log n), O(n^2), O(n^2 log n), O(n^3) or O(2^n).
The measurements are noisy and the sizes vary a lot between tests: exponential datasets only go up to a few dozen, while polynomial ones can reach tens of thousands. One validation dataset is generated from n^2.8 and still expects O(n^3), so the answer is the closest class, not an exact fit.
Approach, step by step
- Read the pointsStore the pairs (n, t). There are at most a few thousand points, so keeping them all in lists is fine and lets you loop over them once per candidate.
- Normalise by each candidateFor every candidate f, compute r = t / f(n) for each point. If t ≈ c·f(n), all r are close to the same constant c; if f grows too slowly r keeps increasing, and if f grows too fast r collapses towards zero.
- Score the flatnessMeasure how constant the ratios are with the squared coefficient of variation: variance(r) / mean(r)². Dividing by the squared mean makes the score independent of the unknown constant c, so candidates with very different magnitudes can be compared fairly.
- Guard the numerically unsafe pointsSkip n = 1 for anything involving log n (log 1 = 0 gives a division by zero) and skip large n for 2ⁿ, because 2.0**n overflows a double past about n = 1023. Only score a candidate when at least a handful of points remain.
- Print the best matchKeep the candidate with the lowest score and print its name in the O(...) format. Ties are not an issue in practice: the scores of neighbouring classes usually differ by orders of magnitude.
Complexity
O(N)O(N)Eight candidates are each scored in one pass over the N points, so the work is 8·N operations. The points are stored once so each candidate can reread them.
Solution code
Bug fixed in this version: The Python block calls sys.maxsize but only imports math, so it raises NameError on every test. It also divides by log(1) = 0 when a dataset starts at n = 1, and its overflow cut-off (maxDataVolume = j-1) silently drops one valid point. The replacement keeps the same ratio-variance idea with those bugs fixed.
Bender - Episode 3 – Python
import math
# candidate complexities, in the order the answer strings are expected
names = ["1", "log n", "n", "n log n", "n^2", "n^2 log n", "n^3", "2^n"]
funcs = [
lambda n: 1.0,
lambda n: math.log(n),
lambda n: float(n),
lambda n: n * math.log(n),
lambda n: float(n) ** 2,
lambda n: float(n) ** 2 * math.log(n),
lambda n: float(n) ** 3,
lambda n: 2.0 ** n,
]
count = int(input())
points = []
for _ in range(count):
num, t = map(int, input().split())
points.append((num, t))
best, best_score = 0, float("inf")
for i, f in enumerate(funcs):
ratios = []
for num, t in points:
if num < 2: # log(1) = 0 would divide by zero
continue
if i == 7 and num > 1000: # 2.0 ** n overflows a double past ~1023
continue
ratios.append(t / f(num))
if len(ratios) < 5:
continue
mean = sum(ratios) / len(ratios)
if mean <= 0:
continue
# squared coefficient of variation: 0 if t is exactly c * f(n)
score = sum((r - mean) ** 2 for r in ratios) / len(ratios) / mean ** 2
if score < best_score:
best, best_score = i, score
print("O({})".format(names[best]))
Common mistakes
- Dividing by log(1)Many datasets start at n = 1, and log(1) = 0. Any candidate containing log n then divides by zero; skip those points rather than adding a tiny epsilon, which would create a huge outlier ratio.
- Overflow on 2ⁿ2.0**n raises OverflowError in Python (and gives Infinity in Java/C) once n exceeds about 1023. Polynomial datasets go far beyond that, so the exponential candidate must ignore those points instead of crashing.
- Using raw varianceThe plain variance of t/f(n) depends on the scale of t/f(n): an n³ candidate has tiny ratios and therefore a tiny variance even when it is wrong. Normalise by the squared mean, or compare logarithms, before comparing candidates.
- The n^2.8 validation testA dataset generated from n^2.8 sits between n² log n and n³. A scoring rule that over-weights small n can pick n² log n; the ratio method on the full range favours n³, which is the expected answer.
Going further
The ratio method has an honest weakness: a constant overhead. If measured times look like 5000 + c·f(n), small-n points are dominated by the 5000, the ratios are no longer flat and the method drifts one class down (n is reported as log n, n log n as n). A quick test with synthetic data shows exactly this. The robust alternative is a log-log least squares fit: regress log t on log n over the upper half of the points, where the overhead is negligible; the slope gives the exponent (0, 1, 2, 3), a slope between integers that is consistently above the integer points to an extra log factor, and a straight line in log t versus n (rather than log n) reveals 2ⁿ. On the CodinGame datasets the simple ratio test is enough, but the log-log fit is what you would use on real benchmarks.
FAQ
Why compare t/f(n) instead of fitting a curve?
If t = c·f(n), dividing by f removes the growth and leaves a constant. Checking how constant the result is needs one pass per candidate and no linear algebra, which is enough to separate eight well-spaced classes.
How do I tell n log n from n?
Over a range like 1 to 10,000, log n grows from 0 to about 9, so t/n still increases clearly for an n log n dataset. The normalised variance captures that drift, as long as you skip n = 1.
Is a least squares fit required?
No. A full least squares fit on the model n^a·b^n·log n is the most general approach, but the ratio test or a log-log slope passes all the tests and is much easier to debug.