Better Big Oh [50 pts] [manually graded]
In a triple-quoted string at the top of your file (just below
your name),
include solutions to this exercise. For each of the following functions:
- State in just a few words what it does in general.
- State and justify (in a few words) its worst-case big-oh runtime.
- Provide an equivalent Python function that is more than a constant-factor faster (so it's worst-case big-oh runtime is in a different function family). The better your solution's big-oh runtime, the more points you get!
- State and prove (in a few words) your better solution's worst-case big-oh runtime.
You should assume that lists all contain at least 5 values, and only integer values. Also, if a function takes two lists, you should assume they are the same length N.
import copy
def slow1(a):
(b, c) = (copy.copy(a), 0)
while (b != [ ]):
b.pop()
c += 1
return c
def slow2(a):
n = len(a)
count = 0
for i in range(n):
for j in range(n):
if (a[i] == a[j]):
count += 1
return (count == n)
def slow3(a, b):
# assume a and b are the same length n
n = len(a)
assert(n == len(b))
result = 0
for c in b:
if c not in a:
result += 1
return result
def slow4(a, b):
# assume a and b are the same length n
n = len(a)
assert(n == len(b))
result = abs(a[0] - b[0])
for c in a:
for d in b:
delta = abs(c - d)
if (delta > result):
result = delta
return result
def slow5(a, b):
# Hint: this is a tricky one! Even though it looks syntactically
# almost identical to the previous problem, in fact the solution
# is very different and more complicated.
# You'll want to sort one of the lists,
# and then use binary search over that sorted list (for each value in
# the other list). In fact, you should use bisect.bisect for this
# (you can read about this function in the online Python documentation).
# The bisect function returns the index i at which you would insert the
# value to keep the list sorted (with a couple edge cases to consider, such
# as if the value is less than or greater than all the values in the list,
# or if the value actually occurs in the list).
# The rest is left to you...
#
# assume a and b are the same length n
n = len(a)
assert(n == len(b))
result = abs(a[0] - b[0])
for c in a:
for d in b:
delta = abs(c - d)
if (delta < result):
result = delta
return result