from timeit import repeat
from math import log
from time import time

def estimate_big_o(fun):
    timings = []
    data_length = 2**5
    while data_length <= 2**14:
        seconds = repeat(
            stmt='%s(%d)' % (fun.__name__, data_length),
            setup='from __main__ import %s' % fun.__name__,
            number=1,
            repeat=4)
        timings.append(min(seconds))
        data_length *= 2
        if sum(seconds) > 10:
            break
    print(list(zip([2**x for x in range(5,15)],timings)))
    fits = compare_fit(timings)
    return min(fits, key=fits.get)

def compare_fit(timings):
    top = 2**(len(timings)+4)
    fits = {}
    reference_functions = {
        'O(1)': lambda n: timings[-1],
        'O(log n)': lambda n: log(n)*(timings[-1]/log(top)),
        'O(n)': lambda n: n*(timings[-1]/top),
        'O(n log n)': lambda n: n*log(n)*(timings[-1]/(top*log(top))),
        'O(n^2)': lambda n: (n**2)*(timings[-1]/top**2)}
    for curve, fun in reference_functions.items():
        reference_timing = [fun(n) for n in (2**x for x in range(5, len(timings)+5))]
        fits[curve] = sum((abs(a-b) for a, b in zip(timings, reference_timing)))
    return fits

def test1(n):
    return len(range(int(log(time()**-3))))

def test2(n):
    return min(range(n))

def test3(n):
    return sum(a+b for a in range(n) for b in range(n))

for test in (test1, test2, test3):
    print(test.__name__, estimate_big_o(test))