Give a tight bound of the nearest runtime complexity class for each of the following code fragments in Big-Oh notation, in terms of the variable N.
In other words, write the code's growth rate as N grows.
Write a simple expression that gives only a power of N using a caret ^ character for exponentiation, such as O(N^2) to represent O(N2) or O(log N) to represent O(log2 N).
Do not write an exact calculation of the runtime such as O(2N3 + 4N + 14).
a)
def mystery1(lis):
result = [0] * (2 * len(lis))
for i in range(len(lis)):
result[2 * i] = lis[i] // 2 + list[i] % 2
result[2 * i + 1] = lis[i] // 2
return result
b)
def mystery2(lis):
for i in range(len(lis) // 2):
j = len(lis) - 1 - i
temp = list[i]
list[i] = list[j]
list[j] = temp
c)
def mystery3(lis):
for i in range(len(lis) - 1, 2):
first = list.pop(i)
list.insert(i + 1, first)
d)
def mystery4(lis):
for i in range(0, len(lis) - 1, 2):
first = lis[i]
lis[i] = lis[i + 1]
list[i + 1] = first
