USE PYTHON3; DO NOT IMPORT ANY PACKAGES

Recall the order of common time complexities:

1. O(1) - constant time

2. O(log n) - logarithmic time

3. O(n) - linear time

4. O(n log n) - linearithmic time

5. O(n^2) - quadratic time

6. O(n^3), O(n^4), etc. - polynomial time

7. O(2^n), O(3^n), etc. - exponential time

Read the source code(below) of 10 python functions, and judge the time complexity of them. Write your answer (as the order 1 - 7) in the complexity_mc() function, which returns your answers as a list of 10 integers. In this list, write your answer to the first function at index 0, second function at index 1, etc.

For each function, if its parameter is n, you can assume it's a non-negative and large integer; if its parameter is a list (lst), you can assume n is the length of this list.

def complexity_mc():

"""

>>> answers = complexity_mc()

>>> isinstance(answers, list)

True

>>> len(answers)

10

>>> all([isinstance(ans, int) and 1 <= ans <= 7

... for ans in answers])

True

"""

# YOUR CODE GOES HERE #

return [...]

SOURCE CODES

# Q01

def q2_01(n):

dictionary = {}

for num in range(0, 100):

if num < n:

dictionary[num] = n - num

# Q02

def q2_02(n):

result = 0

for i in range(300):

result += (3 ** n)

for j in range(n * n * n * n):

result += 2

for k in range(0, 300 * n, 3):

result += 600 * k

return result

# Q03

def q2_03(n):

i = n

for j in range(2 * n):

while i > 1:

i = i // 2

i = n

# Q04

def q2_04(lst):

min_val = lst[0]

for val in lst:

if val < min_val:

min_val = val

return min_val

# Q05

def q2_05(n):

values = []

for i in range(0, n, 1):

for j in range(n, i, -1):

values.append(i + j)

return values

# Q06

def q2_06(n):

while n >= 1:

n = n // 3

for i in range(n * n):

print("Hello")

# Q07

def q2_07(lst):

for i in range(len(lst)):

min_idx = i

for j in range(i + 1, len(lst)):

if lst[j] < lst[min_idx]:

min_idx = j

temp = lst[i]

lst[i] = lst[min_idx]

lst[min_idx] = temp

# Q08

def q2_08(n):

p = n

q = 1

while p >= 1:

print("outer")

while q <= n:

q = q + 1

print("inner")

p = p // 2

print("finished")

# Q09

def q2_09(lst):

for item1 in lst:

for item2 in lst[::-1]:

for i in range(len(lst)+10, len(lst)-10, -1):

print(str(item1) + str(item2) + str(i))

# Q10

def q2_10(n):

def q2_10_helper(n, k):

m = 1

for i in range(n):

print("in helper")

m = m * k

return m

result = 0

for p in range(q2_10_helper(n, 2)):

result = result + p

for q in range(q2_10_helper(n, 3)):

result = result - q

return result