Question

Question 15: Use the Master theorem to find the asymptotic complexity of the running time function T(n) of the program in problem 14.

--- Problem 14 ---

def prob14(L):
if len(L) <= 1:
return 0
output = 0
for x in L:
for y in L:
output += x*y
for x in L:
output += x
left = L[ 0 : len(L)//2 ]
right = L[ len(L)//2 : len(L) ]
return output + prob15(left) + prob15(right)

***Big-O, Omega, Theta complexity of functions, Running time equations of iterative functions & recursive functions,  Substitution method & Master theorem

Please answer within these topics.***

Answer 1

The algorithm you given in question hasn't proper Indentation, so from my intuition I have taken the algorithm as in my solution image below. So match it with your question and let me know in comment section, if any changes required. If you liked the solution, then please LIKE the solution for my motivation.

Still any doubt? do ask in comment section