o-notation.py

from __future__ import print_function
import math

math.lg = lambda x : math.log(x, 2)

# rough approximates, completely disregards the coefficients that might be in
# front of these functions. still, illustrative of their rate of growth as
# n -> \inf

for i in range(1, 20):
    print("# c: {}, logn: {:.2f}, n: {:3}, nlogn: {:7.2f}, n^2: {:4}, n^3: {:5}, 2^n: {:7}".format(
        1, math.lg(i), i, i*math.lg(i), i**2, i**3, 2**i))

# c: 1, logn: 0.00, n:   1, nlogn:    0.00, n^2:    1, n^3:     1, 2^n:       2
# c: 1, logn: 1.00, n:   2, nlogn:    2.00, n^2:    4, n^3:     8, 2^n:       4
# c: 1, logn: 1.58, n:   3, nlogn:    4.75, n^2:    9, n^3:    27, 2^n:       8
# c: 1, logn: 2.00, n:   4, nlogn:    8.00, n^2:   16, n^3:    64, 2^n:      16
# c: 1, logn: 2.32, n:   5, nlogn:   11.61, n^2:   25, n^3:   125, 2^n:      32
# c: 1, logn: 2.58, n:   6, nlogn:   15.51, n^2:   36, n^3:   216, 2^n:      64
# c: 1, logn: 2.81, n:   7, nlogn:   19.65, n^2:   49, n^3:   343, 2^n:     128
# c: 1, logn: 3.00, n:   8, nlogn:   24.00, n^2:   64, n^3:   512, 2^n:     256
# c: 1, logn: 3.17, n:   9, nlogn:   28.53, n^2:   81, n^3:   729, 2^n:     512
# c: 1, logn: 3.32, n:  10, nlogn:   33.22, n^2:  100, n^3:  1000, 2^n:    1024
# c: 1, logn: 3.46, n:  11, nlogn:   38.05, n^2:  121, n^3:  1331, 2^n:    2048
# c: 1, logn: 3.58, n:  12, nlogn:   43.02, n^2:  144, n^3:  1728, 2^n:    4096
# c: 1, logn: 3.70, n:  13, nlogn:   48.11, n^2:  169, n^3:  2197, 2^n:    8192
# c: 1, logn: 3.81, n:  14, nlogn:   53.30, n^2:  196, n^3:  2744, 2^n:   16384
# c: 1, logn: 3.91, n:  15, nlogn:   58.60, n^2:  225, n^3:  3375, 2^n:   32768
# c: 1, logn: 4.00, n:  16, nlogn:   64.00, n^2:  256, n^3:  4096, 2^n:   65536
# c: 1, logn: 4.09, n:  17, nlogn:   69.49, n^2:  289, n^3:  4913, 2^n:  131072
# c: 1, logn: 4.17, n:  18, nlogn:   75.06, n^2:  324, n^3:  5832, 2^n:  262144
# c: 1, logn: 4.25, n:  19, nlogn:   80.71, n^2:  361, n^3:  6859, 2^n:  524288