# CMU 15-112: Fundamentals of Programming and Computer Science Day12 Practice Selected Solutions

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