.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)

You'll get a 16.0KB .DOCX file.