Monday 2/1 Solutions

Exercise 1:

An algorithm that is O(N^3) would be

In [2]:
import numpy as np
import matplotlib.pyplot as plt
In [ ]:
def do_cubic(arr): # arr is length N
    for x in arr: # Takes  a*N*N*N steps
        for y in arr: # Takes a*N*N steps
            for z in arr: # Takes a*N steps
                # Domething that costs at most a

$T(N) = aN^3$

$T(N)$ is $O(N^3)$

Exercise 2

$ f(N) = N^2 \log_2(N) + N^3 $

Claim: $f(N)$ is $O(N^3)$

Fact: $N > \log_2(N), N \geq 1$

Ex) $\log_2(8) = 3$

$\log_2(32) = 5$

In [4]:
N = np.arange(1, 32)
lg2N = np.log2(N)
plt.plot(N, N)
plt.plot(N, lg2N)
plt.legend(["N", "$log_2(N)$"])
Out[4]:
<matplotlib.legend.Legend at 0x294f7a69390>

$ f(N) = N^2 \log_2(N) + N^3 $

$ N^2 \log_2(N) + N^3 \leq cN^3 $

Since $N > \log_2(N)$ when $N \geq 1$

$ N^2 \log_2(N) + N^3 < N^2 * N + N^3 $

$ N^2 \log_2(N) + N^3 < 2N^3 $

$ c = 2 $

Exercise 3

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

In [8]:
N = np.arange(1, 20)
log2N = np.log2(N)
log2NSqr = np.log2(N*N)
plt.plot(N, log2N)
plt.plot(N, log2NSqr)
plt.plot(N, 2*log2N, linestyle='--')
plt.legend(["$\log_2(N)$", "$\log_2(N^2)$", "$2\log_2(N)$"])
Out[8]:
<matplotlib.legend.Legend at 0x294f7c62780>

$ \log_a(x^b) = b \log_a(x) $

$f(N) = \log_2(N^2) = 2 \log_2(N) $

$ O(\log_2(N)) $

Exercise 4

Find an algorithm that is $O(N^2 \log N)$. Sorting algorithms, like merge sort, take

$T(N) = aN \log_2(N) $

In [9]:
def myfunc(arr): # arr length N
    # N*a*N*log(N) = a*N^2*log2(N)
    for i in range(N):
        arr = sorted(arr) # aN log2(N)
In [ ]:
def myfunc2(arr): # arr length N
    arr2 = []
    for i in range(len(arr)):
        arr2 = arr2 + arr
    #arr2 has N^2 elements