Run times for various complexity functions, just for fun

timecomplexity.py

# Runtimes for various complexity functions, sort of.
#
# A hacked-together little Python3 script printing runtimes for various
# complexity functions to standard output.
#
# The script isn't very general or customizable; you have to edit the
# source code to explore different functions or use different values
# of n.

import math
from decimal import Decimal

# Set this value to how fast you want your "computer" to be
# For example, 1000000 for one million abstract operations
# per second.
OPS_PER_SECOND = 1000000

# We're not doing anything less than microseconds
MICROSECONDS_PER_SECOND = 1000000

UNITS = [
    ('µs', 1000),
    ('ms', 1000),
    ('seconds', 60),
    ('minutes', 60),
    ('hours', 24),
    ('days', 365.25),
    ('years', 100),
    ('centuries', 10000000),
    ('Ga', None)]

# I know, I know, if I were cooler this would be output in JSON.
def times(name, f):
    print(name)
    print("-" * 40)
    for n in [10, 20, 50, 100, 1000, 1000000]:
        try:
            ops = Decimal(f(n))
            time = (ops / OPS_PER_SECOND) * MICROSECONDS_PER_SECOND
            for (units, factor) in UNITS:
                if factor is None or time < factor:
                    print("{:7} | {:.10g} {}".format(n, time, units))
                    break
                time /= Decimal(factor)
        except:
            # Yes, you can overflow decimal computations too!
            pass
    print()

times("1", lambda n: 1)
times("log log n", lambda n: math.log2(math.log2(n)))
times("log n", lambda n: math.log2(n))
times("sqrt(n)", lambda n: math.sqrt(n))
times("n", lambda n: n)
times("n log n", lambda n: n * math.log2(n))
times("n^2", lambda n: n * n)
times("1000n^2", lambda n: 1000 * (n * n))
times("n^3", lambda n: n * n * n)
times("n^(log n)", lambda n: n ** math.log2(n))
times("1.001^n", lambda n: Decimal('1.001') ** n)
times("1.01^n", lambda n: Decimal('1.01') ** n)
times("2^n", lambda n: Decimal('2') ** n)
times("n^n", lambda n: Decimal(n) ** n)
times("2^(2^n)", lambda n: Decimal(2) ** (2**n))