Coding Solution

Bender - Episode 3 – CodinGame solution in Python

Hardcomplexity analysiscurve fittingstatisticsfloating pointUpdated
Short answer

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

  1. 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.
  2. 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.
  3. 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.
  4. 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.
  5. 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

TimeO(N)
SpaceO(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

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.

Similar puzzles

★ 5.0 · 16 reviews · 928 users Add to Chrome