Big-\(O\) of Loops#
For each of the below functions, determine the runtime in Big-\(O\).
def funcA(L):
my_sum = 0
for elem in L:
my_sum = my_sum + elem
return my_sum
def funcB(L):
my_sum = 0
for i in range(len(L)*len(L)): # range() and len() are both O(1)
my_sum = my_sum + 1
return my_sum
def funcB1(L):
my_sum = 0
for i in range(len(L)*len(L)): # range() and len() are both O(1)
my_sum = my_sum + sum(L)
return my_sum
def funcC(L):
my_sum = 0
for i in range(len(L)):
for j in range(i, len(L)):
my_sum = my_sum + 1
return my_sum
def funcD(L):
my_sum = 0
for i in range(len(L)):
for j in range(i):
my_sum = my_sum + 1
return my_sum
def funcD1(L):
my_sum = 0
for elem in L:
for elem in L:
for elem in L:
my_sum = my_sum + 1
return my_sum
def funcE(L):
my_sum = 0
for i in range(-5, len(L)):
my_sum = my_sum + 1
return my_sum
def funcF(L):
my_sum = 0
for i in range(-50, len(L), 2):
my_sum = my_sum + 1
return my_sum
def funcG(L):
my_sum = 0
for elem in L:
my_sum = my_sum + elem
for elem in L:
my_sum = my_sum + elem
return my_sum
def funcH(L):
my_sum = 0
for i in range(5):
for elem in L:
my_sum = my_sum + elem
for i in range(len(L)):
for j in range(len(L)):
my_sum = my_sum + 1
return my_sum
def funcI(L):
my_sum = 0
for i in range(999999):
my_sum = my_sum + 1
for elem in L[0: int(len(L)/4)]:
my_sum = my_sum + 1
return my_sum
def funcJ(L):
my_sum = 0
index = 1
while index < len(L):
my_sum = my_sum + 1
index = index*2
return my_sum
def funcK(L):
my_sum = 0
for elem in L:
index = 1
while index < len(L):
my_sum = my_sum + 1
index = index*2
return my_sum
def funcL(L):
my_sum = 0
index = 1
while index < len(L):
for elem in L[0:int(len(L)/2)]:
for i in range(len(L)*len(L)):
for j in range(10000):
my_sum = my_sum + 1
index *= 2
return my_sum