Skip to content

Instantly share code, notes, and snippets.

@johntyree
Created February 10, 2014 03:57
Show Gist options
  • Save johntyree/8910125 to your computer and use it in GitHub Desktop.
Save johntyree/8910125 to your computer and use it in GitHub Desktop.
Big Theta
#!/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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment