Skip to content

part3.md

Latest commit

 

History

History
218 lines (153 loc) · 4.82 KB

part3.md

File metadata and controls

218 lines (153 loc) · 4.82 KB

Part 3: Visualizing Order of Growth

In this part, you'll get to visually experiment with different C values and lower bounds on N in order to show that a function fits a certain order of growth. To start, do some imports:

import pandas as pd
import matplotlib
from matplotlib import pyplot as plt
from math import log2, log10, ceil

Also remember to do %matplotlib inline

Now paste the following code in a cell (you don't need to understand it for the purposes of this lab):

matplotlib.rcParams["font.size"] = 20

def get_ax():
    fig, ax = plt.subplots(figsize=(8,6))
    ax.spines["right"].set_visible(False)
    ax.spines["top"].set_visible(False)
    ax.set_xlim(1, 10)
    return ax

def scale_ax():
    ax = get_ax()
    ax.set_xlabel("N (data size)")
    ax.set_ylabel("Steps")
    return ax

def plot_func(ax, f, C=1, color="k", label="work"):
    start = ax.get_xlim()[0]
    width = ax.get_xlim()[1] - ax.get_xlim()[0]
    s = pd.Series([],dtype=float)
    for i in range(100):
        N = start + width * (i+1)/100
        s[N] = eval(f)
    s.sort_index().plot(ax=ax, color=color, linewidth=3, label=label)
    plt.text(s.index[-1], s.iloc[-1], f, verticalalignment='center')
    
def upper_bound(ax, order, C=1, minN=None):
    f = order
    if C != 1:
        f = "C * (%s)" % order
    plot_func(ax, f, C=C, color="r", label="upper bound")
    if minN != None:
        ax.axvspan(minN, ax.get_xlim()[1], color='0.85')
    ax.legend(frameon=False)

Exercise 1: show N+100 is in O(N).

You need to show that some multiple of N is an upper bound on N+100 for large values of N. Paste+run this code:

ax = scale_ax()
ax.set_xlim(0, 10) # TODO: change upper bound
plot_func(ax, "N + 100")

upper_bound(ax, order="N") # TODO: pass C and minN

It should look like this:

Clearly g(N)=N is not an upper bound on f(N)=N+100, but remember that you are allowed to do the following:

  1. multiple g(N) by a constant C
  2. require that N be large

To use your first capability, pass in a C value of of 25, changing the call to upper_bound(...) to be like this:

upper_bound(ax, order="N", C=25)

It should look like this:

Better, but now the red line is only an upper bound for large N values. Let's set a lower bound on N, like this:

upper_bound(ax, order="N", C=25, minN=6)

It should look like this:

Great!

In general for all of these exercises, your job is to choose C and minN values so that the red line is above the black line in the shaded portion.

Finally, you should make sure the upper bound keeps holding for large N values. If this were a math course, you would prove this is true for all large N values. But since this is a programming course, let's just make the xlim really big and make sure there are no obvious problems, like this:

ax.set_xlim(0, 1e6) # 1 million

Looks good!

Exercise 2: show 100*N is in O(N).

Start with this:

ax = scale_ax()
ax.set_xlim(0, 10)
plot_func(ax, "100*N")

upper_bound(ax, order="N")

Do you need to set minN for this one, or is choosing the right C good enough?

Exercise 3: show N**2 + 5*N + 25 is in O(N**2)

Start with this:

ax = scale_ax()
ax.set_xlim(0, 10)
plot_func(ax, "N**2 + 5*N + 25")

upper_bound(ax, order="N**2")

Exercise 4: try to show 2*N + (N/15)**4 is in O(N)

Start with this:

ax = scale_ax()
ax.set_xlim(0, 10)
plot_func(ax, "2*N + (N/15)**4")

upper_bound(ax, order="N")

Use C=3 and minN=1.

What happens when you increase the x limit to 75?

ax.set_xlim(0, 75)

It turns out 2*N + (N/15)**4 is NOT in O(N) after all. What Big O order of growth does 2*N + (N/15)**4 have?

Exercise 5: show log2(N) is in O(log10(N))

Start with this:

ax = scale_ax()
ax.set_xlim(1, 100)
plot_func(ax, "log2(N)")

upper_bound(ax, order="log10(N)")

Any C value that is at least log2(10) will work here. In general, any log curve with base M is just a constant multiple of another log curve with base N. Thus, it is common to just say an algorithm is O(log N), without bothering to specify the base.

Exercise 6: show ceil(log2(N)) is in O(log N)

Start with this:

ax = scale_ax()
ax.set_xlim(1, 100)
plot_func(ax, "ceil(log2(N))")

upper_bound(ax, order="log2(N)")

Exercise 7: show N * ceil(log2(N)) is in O(N log N)

Start with this:

ax = scale_ax()
ax.set_xlim(1, 100)
plot_func(ax, "N * ceil(log2(N))")

upper_bound(ax, order="N * log2(N)")

Exercise 8: show F(N) = 0+1+2+...+(N-1) is in O(N**2)

Replace ???? in the following:

ax = scale_ax()
ax.set_xlim(1, 100)
plot_func(ax, "sum(range(int(N)))")

upper_bound(ax, order=????)