# CMU 15-112 Fall 2016: Fundamentals of Programming and Computer Science Lab 7 (Due Thursday 13-Oct, at 10pm, no extensions or grace days)

• This lab is Collaborative. No solo work allowed. Work in groups of 2-3 (and the same group the whole time). See the syllabus for more details.
• Starter file: cs112_f16_wk7.py
• This week you may use up to 6 submissions. Only your last submission counts. There is no autograder this week.
• Do not use recursion this week.
• Do not hardcode the test cases in your solutions.

1. 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:
1. State in just a few words what it does in general.
2. State and prove (in a few words) its worst-case big-oh runtime.
3. 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!
4. 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
# 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
```