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