Big Theta

big_O.py

#!/usr/bin/env python2
# GistID: 8910125

from numpy import array, log, linspace
from matplotlib import pyplot as plt

# http://en.wikipedia.org/wiki/Big_o_notation#Family_of_Bachmann.E2.80.93Landau_notations  # noqa
n = linspace(1, 100)
fn = log(n) / log(5)  # log_5(n)
gn = log(n) / log(3)  # log_3(n)
k1 = log(3) / log(5) * 0.9  # clearly less than fn
k2 = log(3) / log(5) * 1.1  # clearly less than fn
data = array([gn * k2, fn, gn * k1])
column = ('gn * k2', 'fn', 'gn * k1')
plt.plot(n, data[0], label=column[0])
plt.plot(n, data[1], label=column[1])
plt.plot(n, data[2], label=column[2])
plt.title("$f(n) = \Theta(g(n))$")
plt.xlabel("n")
plt.legend(loc='best')
plt.show()

# http://i.imgur.com/19rQ1eZ.png