Efficiency Practice

1. Big-O Analysis: Problems and Solutions
   Find the Big-O runtime of the given function by computing the runtime of each line.
   
   The solutions are below, but try your best to solve it yourself before looking at the solutions.
   
   

   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))



2. 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()


3. 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()


4. 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.