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 \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.

Difficulty: Hard · Skills: complexity analysis, curve fitting, statistics, floating point

What this puzzle tests in a coding interview

Bender, Algorithmic Complexity asks you to guess the complexity class of a program from measured timings. It tests whether you can choose a sound fitting criterion and handle numerical issues such as overflow and noisy data.

How to solve it, step by step

  1. Read the pairs of data volume and execution time.
  2. List the candidate functions: 1, log n, n, n log n, n squared, n squared log n, n cubed and 2 to the n.
  3. For each candidate, compute the ratio of measured time to the function value for each data point, skipping huge inputs for 2 to the n to avoid overflow.
  4. Measure how stable the ratios are by computing their variance divided by the squared mean.
  5. Print the candidate with the most stable ratio, written as O of that function.

Time and memory complexity

Each candidate scans all n points, so time is O(8 x n) and memory is O(n).

Traps to avoid

Tip for a timed test

Normalised variance of the ratio is a five-line method that passes most tests; a log-log least squares fit is the more rigorous answer to mention if the interviewer asks.

Python

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]))