The aim of this puzzle is to match a scatterplot with one of a few complexity functions. As these functions have a \(x \mapsto x^{\alpha} \beta^x \log{x} \) form, one of the most complete solution would be to use the method of least squares. But for this puzzle, you can settle for a lighter method, for example computing the scatterplots corresponding to the complexity functions, and find a formula to assess their likelihood to the original scatterplot.
Note that the \(\Theta (n^3)\) validation test can be tricky to pass with this method, as the data set is a \(\Theta(n^{2.8})\) which is closer to a \(\Theta (n^2 \log{n})\) on the interval studied. A hack around this is to add the \(\Theta(n^{2.5})\) complexity function, and output \(\Theta (n^3)\) when it is recognized.
import math
# name, and function of the main complexities
names = ["1","log n","n","n log n", "n^2", "n^2 log n", "n^3", "2^n"]
complexities = [lambda x: 1,
lambda x: math.log(x),
lambda x: x,
lambda x: x*math.log(x),
lambda x: x**2,
lambda x: x**2*math.log(x),
lambda x: x**3,
lambda x: math.pow(2,x)]
# maximum value which can be fed to the corresponding complexity function
# without overflow
upperLimit = [None, None, None, None, None, None, None, 500]
# Read input, storing data volumes in x, and execution times in perf
x, perf = [], []
for i in range(int(input())):
a, b = [int(j) for j in input().split()]
x.append(a)
perf.append(b)
# for each complexity function f, computes a normalized variance of the ratio (perf/f)
# It it is not representative (variance over less than 5 values) stores -1 instead
# Then updates minVariance and result so that minVariance stays the minimal
# representative variance found yet, and result is the number of the corresponding
# function, which is the most probable complexity function found yet
variances, minVariance, result = [], sys.maxsize, -1
for i in range(len(complexities)):
f = complexities[i]
# takes upperLimit into account to avoid an overflow
maxDataVolume = len(x)
if upperLimit[i] != None:
for j in range(len(x)):
if x[j] > upperLimit[i]:
maxDataVolume = j-1
break
ratio = [ perf[j]/f(x[j]) for j in range(maxDataVolume)]
if (len(ratio) < 5):
variances.append(-1)
else:
mean = sum(ratio) / len(ratio)
variances.append(sum([(val-mean)**2 for val in ratio]) / mean**2)
if (variances[-1] < minVariance):
minVariance = variances[-1]
result = i
print("O({})".format(names[result]))