Bender, Algorithmic Complexity

The aim of this puzzle is to match a scatterplot with one of a few complexity functions. As these functions have a x↦xαβxlogx 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 Θ(n3) validation test can be tricky to pass with this method, as the data set is a Θ(n2.8) which is closer to a Θ(n2logn) on the interval studied. A hack around this is to add the Θ(n2.5) complexity function, and output Θ(n3) when it is recognized.

Python

  1. import math
  2.  
  3. # name, and function of the main complexities
  4. names = ["1","log n","n","n log n", "n^2", "n^2 log n", "n^3", "2^n"]
  5. complexities = [lambda x: 1, 
  6.                 lambda x: math.log(x), 
  7.                 lambda x: x, 
  8.                 lambda x: x*math.log(x), 
  9.                 lambda x: x**2, 
  10.                 lambda x: x**2*math.log(x),
  11.                 lambda x: x**3, 
  12.                 lambda x: math.pow(2,x)]
  13. # maximum value which can be fed to the corresponding complexity function
  14. # without overflow
  15. upperLimit = [None, None, None, None, None, None, None, 500]
  16.  
  17. # Read input, storing data volumes in x, and execution times in perf
  18. x, perf = [], []
  19. for i in range(int(input())):
  20.     a, b = [int(j) for j in input().split()]
  21.     x.append(a)
  22.     perf.append(b)
  23.  
  24. # for each complexity function f, computes a normalized variance of the ratio (perf/f)
  25. # It it is not representative (variance over less than 5 values) stores -1 instead
  26. # Then updates minVariance and result so that minVariance stays the minimal 
  27. # representative variance found yet, and result is the number of the corresponding 
  28. # function, which is the most probable complexity function found yet
  29. variances, minVariance, result = [], sys.maxsize, -1
  30.  
  31. for i in range(len(complexities)):
  32.     f = complexities[i]
  33.     # takes upperLimit into account to avoid an overflow
  34.     maxDataVolume = len(x)
  35.     if upperLimit[i] != None:
  36.         for j in range(len(x)):
  37.             if x[j] > upperLimit[i]:
  38.                 maxDataVolume = j-1
  39.                 break
  40.             
  41.     ratio = [ perf[j]/f(x[j]) for j in range(maxDataVolume)]
  42.     if (len(ratio) < 5):
  43.         variances.append(-1)
  44.     else:
  45.         mean = sum(ratio) / len(ratio)
  46.         variances.append(sum([(val-mean)**2 for val in ratio]) / mean**2)
  47.         if (variances[-1] < minVariance):
  48.             minVariance = variances[-1]
  49.             result = i
  50.  
  51. print("O({})".format(names[result]))
  52.