Question

Question 14: Find the running time function, T(n), of the program below.

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)

​

ANSWER:

T(n) = ...

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

HI ,

First of all ,

In above code prob15 is not defined .

If you have prob15 functionality or code please mention in comment. So i can write the function or add into this.

find the code with prob14 instead of prob15 in retiurn statement. -

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 + prob14(left) + prob14(right)

arr=[1,5,4,3,2]
print(prob14(arr))

output -

If you have anything , Feel free to mention in comment box,