# CMU 15-112 Summer 2018: Fundamentals of Programming and Computer Science Homework 9 (Due Tue 12-Jun, at 5pm)

• This assignment is SOLO. This means you may not look at other student's code or let other students look at your code for these problems. See the syllabus for details.

• To start:
1. Create a folder named 'week4'
2. Edit hw9.py using Pyzo
3. When you are ready, submit hw9.py to Autolab. For this hw you will have 20 submissions.
• This homework is partially autograded. You will receive feedback for some of the problems after the deadline.
• Do not use recursion in this assignment.
• Do not hardcode the test cases in your solutions.
• This homework may be graded for style.

1. Big-O Calculation [36pts] [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. Write the Big-O time or number of loops for each line of the program, then state the resulting Big-O of the whole program.
3. Provide an equivalent Python function that is more than a constant-factor faster (so its worst-case Big-O runtime is in a different function family). The better your solution's Big-O runtime, the more points you get!
4. Write the Big-O time or number of loops for each line of the new program, then state the resulting Big-O of the whole program.

```def slow1(lst): # N is the length of the list lst
assert(len(lst) >= 2)
a = lst.pop()
b = lst.pop(0)
lst.insert(0, a)
lst.append(b)

def slow2(lst): # N is the length of the list lst
counter = 0
for i in range(len(lst)):
if lst[i] not in lst[:i]:
counter += 1
return counter

import string
def slow3(s): # N is the length of the string s
maxLetter = ""
maxCount = 0
for c in s:
for letter in string.ascii_lowercase:
if c == letter:
if s.count(c) > maxCount or \
s.count(c) == maxCount and c < maxLetter:
maxCount = s.count(c)
maxLetter = c
return maxLetter
```

```assert(invertDictionary({1:2, 2:3, 3:4, 5:3}) ==