# CMU 15-112: Fundamentals of Programming and Computer Science Week8 Efficiency Practice (Due never)

 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) for i in range(1, len(sorted(L)) + 1): # initial computation of O(nlogn), # then runs O(n) times 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))```