Complexity Hierarchies And Little-o Notation

In [1]:
import numpy as np
import matplotlib.pyplot as plt

Hypothesizing Hierarchies via Plotting

Let's first look at a plot of different functions that are commonly used to describe the complexity of algorithms in big O notation. We're interested in long time behavior, so it appears that the hierarchy is

$ 1 < \log(N) < N < N^2 < N^3 < 2^N < N! $

But we need some mathematical tools to prove this

In [2]:
def fac(N):
    # fac(N) = N*(N-1)*(N-2)*...*1
    res = 1
    for i in range(1, N+1):
        res *= i
    return res
In [3]:
N = np.arange(1, 20)
plt.plot(N, N) # N
plt.plot(N, N**2) #N^2
plt.plot(N, N**3) #N^3
plt.plot(N, np.ones(len(N))) # Constant
plt.plot(N, np.log2(N))
plt.plot(N, 2**N) # Exponential, 2^N
plt.plot(N, [fac(i) for i in N]) # N!
plt.legend(["$N$", "$N^2$", "$N^3$", "$1$", "$\log_2(N)$", "$2^N$", "$N!$"])
plt.yscale("log")
plt.xlabel("N")
Out[3]:
Text(0.5, 0, 'N')
In [ ]: