- Code #1:
def bigO1(L): # L is a list of length N
count = 0 # O(_)
for i in range(len(L)): # loops _ times
count += L[i] # O(_)
return count # O(_)
# Overall - O(_)
- Code #2:
def bigO2(L): # L is a list of length N
i = 1 # O(_)
listLength = len(L) # O(_)
result = [] # O(_)
while i < listLength: # loops _ times
result += L[i] # O(_)
i *= 3 # O(_)
return result # O(_)
# Overall - O(_)
- Code #3:
def bigO3(L): # L is a list of length N
result = 0 # O(_)
for elem in L: # loops _ times
result += L.count(elem) # O(_)
return result # O(_)
# Overall - O(_)
- Code #4:
def bigO4(a): # a is a list of length N
for i in range(len(a)): # loops _ times
j = 1 # O(_)
while j < len(a): # loops _ times
j *= 2 # O(_)
return a # O(_)
# Overall - O(_)
- Code #5:
def bigO5(n):#n is an int, N= n #Big-O
ret = [] #______
for i in range(n): #______
for j in range(i+1,n): #______
ret.append(i+j) #______
return ret #______
- Code #6:
def bigO6(L): #L contains N items # Big-O
allowedWords =["surround", "friend", "stop"] #______
newList = [] #______
for w in L: #______
if w in allowedWords: #______
newList.append(w) #______
for w in allowedWords: #______
if w in L: #______
L.remove(w) #______
L.sort() #______
L.extend(newList) #______
return L #______
- Code #7:
def bigO7(L, z):
n = len(L)
a = max(L)
for x in range(n):
a += x
return a
Big-O: ______________
Explanation: _____________
- Code #7:
def bigO7(L, z):
n = len(L)
a = max(L)
for x in range(n):
a += x
return a
Big-O: ______________
Explanation: _____________
- Code #8:
def bigO8(L, z):
a = max(len(L)-1, z)
L[0] += L[a]
return max(L[a],z)
Big-O: ______________
Explanation: _____________
- Code #9:
def bigO9(L, z):
n = len(L)
x = 0
y = 0
while (x < n):
while (y < n):
y += 1
z += y
x += 1
z += x
return z
Big-O: ______________
Explanation: _____________
- Code #10:
def bigO10(L,z):
for i in range(len(L)):
if L[i] == sorted(L)[z]:
return i
return False
Big-O: ______________
Explanation: _____________
- Short Answer
Consider the following code:
def f(a):
t = 0
for e in a:
for t in a:
t = t + 1
return t
Big-O time efficiency of the function if:
- a is a list. _________________________________
- a is a set. _________________________________
- a is a dict. _________________________________
- a is a 5-letter english word (string). _____________________
- cheapestProducts(priceList) (Efficient)
Write the function cheapestProducts(priceList) which, given a list of tuples each containing the product name, store
name, and price of a product, returns a dictionary mapping product names to a tuple containing the store and price
for the lowest price found for the item. In the event of a tie, either store may be used. Consider the following
example. If
productList = [ ("X-Box", "LuLu", 1200), ("iPhone XR", "Carrefour", 3000), ("Washer", "SafariMart" , 799), ("iPhone XR", "Al Anees" , 2870), ("Washer", "LuLu", 899) ]
cheapestProducts(priceList)
returns a dictionary containing...
{'X-Box': (1200, 'LuLu'), 'iPhone XR': (2870, 'Al Anees'), 'Washer': (799, 'SafariMart')}
Your solution must run in O(N) time, where N = len(productList).
- findFlukeNumbers(L)(Efficient)
A fluke number (coined term) is an integer that has a frequency in the list equal to its value Write the function
findFlukeNumbers(L)) that is given a list L of objects (not necessarily integers). The function should return a set
containing all the fluke numbers in the list. Your solution should run in O(N) time. For example,
assert(findFlukeNumbers([1,'a','a',[4], 3, False, 3, 3]) == {1, 3})
assert(findFlukeNumbers([1, 2, 2, 3, 3, 3, 4]) == {1, 2, 3})
assert(findFlukeNumbers([0, False, 'hello']) == set())
- Improve the Efficiency! : I
The following function returns the number of elements in L that also have their square in L.
def countSquares(L):
count = 0
for item in L:
square = item**2
if item !=square and square in L:
count += 1
return count
- What is the Big-O efficiency o this function?
- The function is less efficient than it could be. Briefly describe how to change the function to make it more
efficient without completely changing the algorithm. Your answer must change the function family of the program’s
runtime. Also state the Big-O efficiency the function with your changes.
- Improve the Efficiency : II
Given the function f(L) below which takes a list L containing N integers, write the function g(L) such that:
- g(L) works identically to f(L) for any list L with N integers.
- g(L) runs in O(N) time.
def f(L):
if L == [ ]:
return None
M = [ ]
for v in L:
if v not in M:
M.append(v)
N = sorted([L.count(v) for v in M])
return N[-1]
- getPairSum(a, target)
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). (or just do the O(n) one)
- mostCommonName (L)
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). (or just do the O(n) one)
- sameXandY(L)
Write the function sameXandY(L) that takes a list L that contains n (x, y) tuples, and returns True if every x value
occurs as some y value and every y value also occurs as some x value, and False otherwise. If the list is empty,
return False. Note: To receive full credit, your function must run in O(n) where n is the length of L. For example:
assert(sameXandY([(1,2),(2,3),(3,2),(1,1)]) == True) Here, the x values are 1, 2, 3, 1, and the y values
are 2, 3, 2, 1. This meets the requirement, so the function returns True. As another example: assert(sameXandY([(1,2),(2,3),(3,2),(4,1)]) == False)
Here, the x values are 1, 2, 3, 4, and the y values are 2, 3, 2, 1. Since the x value 4 does not occur as a y value,
the function returns False.
def testSameXandY():
assert(sameXandY([ ]) == False)
assert(sameXandY([(1,2)]) == False)
assert(sameXandY([(2,2)]) == True)
assert(sameXandY([(1,2),(2,1)]) == True)
assert(sameXandY([(1,2),(2,3)]) == False)
assert(sameXandY([(1,2),(2,3),(3,2),(1,1)]) == True)
assert(sameXandY([(1,2),(2,3),(3,2),(4,1)]) == False)
- getZeroPair(L)
Write the function getZeroPair(L) which takes a list L of integers, and returns a set of two different integers in L
that sum to zero. If no such pair exists, the function returns None. If there is more than one valid pair, you can
return any of them. For example, getZeroPair([1, 2, 3, 10, -3]) should return the set {-3, 3} since these
sum to 0. getZeroPair([1, 2, 3, 10]) should return None since there is no pair of numbers in [1, 2, 3, 10]
that sums to 0. Your solution must run in no worse than O(N) time, where N is the length of L.
def testGetZeroPair():
assert(getZeroPair([1, 2, 3, 10, -3]) == {-3, 3})
assert(getZeroPair([1, 2, 3, 10]) == None)
assert(getZeroPair([-1, 2, 3, 0, 1]) == {-1, 1})
assert(getZeroPair([-1, 2, -3, 0, -2]) == {-2, 2})
assert(getZeroPair([0, 1, 2, 3, 0]) == None) #Integers must be different
assert(getZeroPair([]) == None)