CMU 15-112: Fundamentals of Programming and Computer Science
Week7 Practice (Due never)
Big-O Analysis: Problems and Solutions
Find the Big-O runtime of the given function by computing the runtime of each line.
| Problems | |
| Mild | |
| Problem 1 | def foo(L): #L is a list
i = 1
listLength = len(L)
result = []
while i < listLength:
result += L[i]
i *= 3
return i |
| Problem 2 | def foo(S): #S is a string
stringLength = len(S)
i = stringLength
result = {}
while i > 0:
result.add(S[i])
i //= 3
return result |
| Problem 3 | def foo(L): # L is a list
lenList = len(L)
count = 0
for i in range(lenList):
for j in range(lenList):
count += L[i]
return count |
| Medium | |
| Problem 4 | def foo(s): #s is a string of length N
result = 0
for char in string.ascii_lowercase:
if char in s:
s = s[1:]
result += 1
return result |
| Problem 5 | def foo(s):
return len(s) |
| Problem 6 | def foo(L): #L is a list
n = len(L)
for i in range(n**2, n**3, n):
L.append(i)
for j in range(n//5, n//2, n//10):
L.pop()
return L |
| Spicy | |
| Problem 7 | def foo(L):
result = []
for i in range(1, len(sorted(L)) + 1):
newList = len(L) * [i]
result.extend(newList)
return sorted(result) |
| Problem 8 | def foo(L): # L is a square, 2D list
n = len(L)
j = 1
count = 0
while j < n:
for i in range(n):
if max(L[j]) in L[i]:
count += 1
j *= 2
return count |
| Problem 9 | def bigOh(L):
new = list()
for i in range(len(L)):
new.extend(L[:i:2])
new.sort()
result = set(new)
return result
|
| Solutions | |
| Mild | |
| Problem 1 | def foo(L): #L is a list
i = 1 # O(1)
listLength = len(L) # O(1)
result = [] # O(1)
while i < listLength: # O(log(N))
result += L[i] # O(1)
i *= 3 # O(1)
return i # O(1)
# Overall -- O(log(N)) |
| Problem 2 | def foo(S): #S is a string
stringLength = len(S) # O(1)
i = stringLength # O(1)
result = {} # O(1)
while i > 0: # O(log(N))
result.add(S[i]) # O(1)
i //= 3 # O(1)
return result # O(1)
# Overall -- O(log(N)) |
| Problem 3 | def foo(L): # L is a list
lenList = len(L) # O(1)
count = 0 # O(1)
for i in range(lenList): # O(N)
for j in range(lenList): # O(N)
count += L[i] # O(1)
return count # O(1)
# Overall -- O(N ** 2) |
| Medium | |
| Problem 4 | def foo(s): #s is a string of length N
result = 0 #O(1)
for char in string.ascii_lowercase: #O(1)
if char in s: #O(N)
s = s[1:] #O(N)
result += 1 #O(1)
return result #O(1)
#Overall - #O(N) |
| Problem 5 | def foo(s):
return len(s) # O(1)
# Overall O(1) |
| Problem 6 | def foo(L): #L is a list
n = len(L) #O(1)
for i in range(n**2, n**3, n): #O(n**2)
L.append(i) #O(1)
for j in range(n//5, n//2, n//10): #O(1)
L.pop() #O(1)
return L #O(1)
#Overall: O(n**2) |
| Spicy | |
| Problem 7 | def foo(L):
result = [] # O(1)
# initial computation of O(nlogn), then runs O(n) times
for i in range(1, len(sorted(L)) + 1): # O(nlogn) + n iterations
newList = len(L) * [i] # O(n)
result.extend(newList) # O(n)
# result has length O(n**2)
return sorted(result) # n**2 log(n**2)
# Overall O(n**2 log(n)) |
| Problem 8 | def foo(L): # L is a square, 2D list
n = len(L) #O(1)
j = 1 #O(1)
count = 0 #O(1)
while j < n: #O(logn)
for i in range(n): #O(n)
if max(L[j]) in L[i]: #O(n)
count += 1 #O(1)
j *= 2 #O(1)
return count #O(1)
#Overall: O(n**2logn) |
| Problem 9 | def bigOh(L):
new = list() # O(1)
for i in range(len(L)): # n times
new.extend(L[:i:2]) # O(i) = O(n)
new.sort() # O(n^2 log(n))
result = set(new) # O(n^2)
return result # O(1)
# O(n^2 log(n)) |
Free Response: Sets, Dictionaries, and Efficiency
-
mostCommonName(L) in O(n) time
Write the function mostCommonName, that takes a list of names (such as ["Jane", "Aaron", "Cindy", "Aaron"], and returns the most common name in this list (in this case, "Aaron"). If there is more than one such name, return a set of the most common names. So mostCommonName(["Jane", "Aaron", "Jane", "Cindy", "Aaron"]) returns the set {"Aaron", "Jane"}. If the set is empty, return None. Also, treat names case sensitively, so "Jane" and "JANE" are different names. You should write three different versions, one that runs in O(n**2), O(nlogn) and O(n).def mostCommonName(L): return 42 # place your answer here! def testMostCommonName(): print("Testing mostCommonName()...", end="") assert(mostCommonName(["Jane", "Aaron", "Cindy", "Aaron"]) == "Aaron") assert(mostCommonName(["Jane", "Aaron", "Jane", "Cindy", "Aaron"]) == {"Aaron", "Jane"}) assert(mostCommonName(["Cindy"]) == "Cindy") assert(mostCommonName(["Jane", "Aaron", "Cindy"]) == {"Aaron", "Cindy", "Jane"}) assert(mostCommonName([]) == None) print("Passed!") testMostCommonName() -
getPairSum(a, target) in O(n) time
Write the function getPairSum(a, target) that takes a list of numbers and a target value (also a number), and if there is a pair of numbers in the given list that add up to the given target number, returns that pair, and otherwise returns an empty list. If there is more than one valid pair, you can return any of them. You should write two different versions, one that runs in O(n**2) and the other in O(n). For example:getPairSum([1],1) == [] getPairSum([5,2],7) in [ [5,2], [2,5] ] getPairSum([10,-1,1,-8,3,1], 2) in [ [10,-8], [-8,10] ] (can also return [-1,3] or [1,1]) getPairSum([10,-1,1,-8,3,1],10) == []
def getPairSum(a, target): return 42 # place your answer here! def testGetPairSum(): print("Testing getPairSum...", end="") assert(getPairSum([1],1) == []) assert(getPairSum([5, 2], 7) in [ [5, 2], [2, 5] ]) # (can return [10, -8] or [-1,3] or [1,1]) assert(getPairSum([10,-1,1,-8,3,1], 2) in [[10, -8], [-8, 10], [-1, 3], [3, -1], [1, 1]]) assert(getPairSum([10,-1,1,-8,3,1], 10) == []) assert(getPairSum([1, 4, 3], 2) == []) print("Passed!") testGetPairSum() - mergeSortWithOneAuxList(a)
Write the function mergeSortWithOneAuxList(a) that works just like mergeSort from the notes, only here you can only create a single aux list just one time, rather than once for each call to merge. To do this, you will need to create the aux list in the outer function (mergeSortWithOneAuxList) and then pass it as a parameter into the merge function. The rest is left to you. In a comment at the top of this function, include some timing measurements comparing this function to the original mergeSort, and a brief reflection on whether or not this change was worthwhile.