.DOCX

# Express the complexity of these functions using the big-O notation

1.          Express the complexity of these functions using the big-O notation: a.   T(n) = 2n2 + 3n3

b.   T(n) = 5 + n

2.          Use the definition of big-O to show that T(n) = 5 + n3  O(n3)

3.          Write down the running time function of the following Python function. Then describe it in terms of O and 

def h(a_list)

n = len(a_list) i = n-1

sum = 0

while i=0 do:

i = i – 1 j = 0

while j<n do:

j = j*2

sum = sum + a_list[i] + a_list[j]

4.          Write down the running time function of the following Python function. Then describe it in terms of O and .

def g(a_list)

n = len(a_list) sum = 0

for i in range(n):

for j in range(n*n):

for k in range(j):

sum = i + j + a_list[i]

5.          Write down the running time function of the following Python function. Then describe it in terms of O and .  (Assume that the running time of function foo is n*log(n).)

def bar(a_list)

n = len(a_list) sum = 0

for i in range(n):

sum = sum + a_list[i] value = 1

for j in range(n*n):

value = value * j

foo(sum, value)