Problem 3

Find the tight-bound complexity of this program. Here, the input size, , is the total number of items in both input lists, A and B.

[2]:

#

# Input : two lists of numbers A and B

# Output : another list of numbers

#

def prob3(A, B):

 output = []

 for x in A:

 output += x*x

 for y in B:

 output += y*y*y

 return output

Problem 4

Use substitution to find the tight-bound complexity of this function: T(n) = 13 + T(n-1), and T(0) = 13.

Show all the steps of your work.