Python question Analysis: Computational Complexity (Q14-15) In this section, you are asked to analyse the worst-case computational time complexity of Python functions. Always identify the order of growth in the tightest and simplest possible form using big-O notation, e.g., write O(n) instead of O(2n+n/2). Question 14 (Complexity 1) State the overall worst-case time complexity of the below function and provide a short explanation of your answer. The function accepts an integer n as input. def mystery(n): num = 1 count = 0 while num < n: num = num*2 count += 1 return count Question 15 (Complexity 2) State the overall worst-case time complexity of the below function and provide a short explanation of your answer. The function is supposed to return a list, res, containing the duplicated elements in the given list , lst, of size n. Analyse the function in terms of the length of the list, n. def duplicate_values(lst): res = [] for i in range(len(lst)): if lst[i] in lst[i+1:]: res.append(lst[i]) return res
Python question
Analysis: Computational Complexity (Q14-15)
In this section, you are asked to analyse the worst-case computational time complexity of Python functions. Always identify the order of growth in the tightest and simplest possible form using big-O notation, e.g., write O(n) instead of O(2n+n/2).
Question 14 (Complexity 1)
State the overall worst-case time complexity of the below function and provide a short explanation of your answer. The function accepts an integer n as input.
def mystery(n):
num = 1
count = 0
while num < n:
num = num*2
count += 1
return count
Question 15 (Complexity 2)
State the overall worst-case time complexity of the below function and provide a short explanation of your answer. The function is supposed to return a list, res, containing the duplicated elements in the given list , lst, of size n. Analyse the function in terms of the length of the list, n.
def duplicate_values(lst):
res = []
for i in range(len(lst)):
if lst[i] in lst[i+1:]:
res.append(lst[i])
return res
Step by step
Solved in 3 steps
