Formal Definition of Big-O

Click here to see my CS 271 notes on this topic, which include an interactive "build your own definition (BYOD)" applet

import numpy as np
import matplotlib.pyplot as plt

Big-O is a notation/concept for upper bounding the time complexity of an algorithm

Def. Big-O A function $f(N)$ is $O(g(N))$ if there exists a constant $c > 0$ so that for all $N > M_c$, $f(N) \leq cg(N)$

I can scale $g$ up so that eventually (in the limit) it will completely beat $f$ on every input

Ex) $f(N) = N + N \log N$

$g(N) = N^{3/2}$

Claim: $f(N)$ is $O(g(N))$

N = np.arange(1, 20)
f = N + N*np.log(N)
c = 1
g = N**1.5
plt.plot(N, f)
plt.plot(N, c*g)
plt.xticks(N);
plt.xlabel("N")
plt.legend(["$f(N)$", "${}*g(N)$".format(c)])

<matplotlib.legend.Legend at 0x7fc379391050>

Ex) I sort a bunch of pixels in an $N \times N$ image, and then I average the x coordinate for the smallest 10% of them

$f(N) = N^2 \log(N^2) + 0.1*N^2$

$f(N) = 2 N^2 \log(N) + 0.1*N^2$

Claim: $f(N)$ is $O(N^2 \log N)$

N = np.arange(1, 20)
f = 2*N*N*np.log2(N) + 0.1*np.log2(N)
c = 2.1
g = N*N*np.log2(N)
plt.plot(N, f)
plt.plot(N, c*g)
plt.xticks(N);
plt.xlabel("N")
plt.legend(["$f(N)$", "${}*g(N)$".format(c)])

<matplotlib.legend.Legend at 0x7fc3409d5250>

If $N \geq 2$, then $\log_2(N) \geq 1$

$f(N) = 2 N^2 \log_2(N) + 0.1*N^2 \leq 2 N^2 \log_2(N) + 0.1*N^2 \log_2(N)$

$f(N) \leq 2.1 N^2 \log_2(N)$, given that $N \geq 2$

c = 2.1, M = 2, satisfying definition

Walk away with two takeaways:

1. The dominant terms are the ones that we use to create our $g(N)$
2. Constants don't matter when we're trying to understand the scaling behavior