Question

Problem 10 Write down the running time function, T(n), of the program below.

def prob10(L):

    s = 0

    for x in L:

        for y in L:

            if x+y % 10 == 0:

                print(x, y, x+y)

                s = s + x*y

    return s

​

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

for given function time complexity will be:

linear complexity will be 4.

T(n)=O(n²) for Big-O

considering two loops will be result in n^2.

for if condition it will be 1

    s = 0                         ->   1

    for x in L:                   ->   n

        for y in L:               ->   n

            if x+y % 10 == 0:     ->   1

                print(x, y, x+y)  ->   1

                s = s + x*y       ->   1 

    return s                      ->   1

T(n)=1+(n*n) +1+1+1+1

      =5+n²

So, by this way f(n) will be:

f(n)=n²+5

f(n)=c.g(n)

let assume c=5 and g(n) will be higher order so it will be n²

n²+5=5(n²)

let n be 1

:1²+5=5(1²)

:6=5

check for 2

:2² +5=5(2²)

:9=20

here it satisfy with n=2

then it is clearly declared it's O(n²) when ∀ n>=2

Therefore, f(n)=O(n²) ∀ n>=2.

2) For Recursive Function

Recursive function takes O(m) Space and if Depth is n then it will be n.

So, therefore it will be O(nm).

3) Substitution Method

In this Method we need to prove the assumed solution.

We make a guess first then try for mathematical induction to prove whether it is right or wrong

Suppose, T(n)=2T(n/2)+n

We assume that T(n)<=cnLogn.

T(n)=2T(n/2)+n

=2cn/2Log(n/2)+n

=cnLog(n)-cnLog2+n

<=cLogn ∀ < n.