Faculty of Arts & Science
Fall 2024 Quiz 9 - V1
CSC 110 Y1F
Question 1. Multiple Choice Questions [3 marks] Part (a) [1 mark]
def f1(numbers: list[int]) -> None:
for i in range(len(numbers)):
numbers[i] = i + 1
for j in range(10):
print(j)
Which of the following is an appropriate exact step count for the total steps the above function takes (letting n be len(numbers))?
(a) n · 10
(b) n · n + 10 · 1 (c) n + 10
(d) None of these options Part (b) [1 mark]
def f2(numbers: list[int]) -> int:
sum = 0
for i in range(len(numbers)):
for j in range(i):
sum = sum + j
return sum
Which of the following is an appropriate, final exact step count for the total steps the above function takes in terms of input size (letting n be len(numbers))?
(a) 1+ n · i +1 (b) 1+ n + i +1 (c) 1+ n · n +1
(d) None of these options Part (c) [1 mark]
def f3(numbers: list[int]) -> list:
new = []
for i in range(len(numbers)):
new.insert(i, numbers[i])
return new
Which of the following is an appropriate, final exact step count for the total steps the above function takes in terms of input size (letting n be len(numbers))?
(a) 1+(n * n)+1
(b) 1+(n + n)+1 (c) 1+(n * 1) + 1
(d) 1+ 2/n(n+1) +1
(e) 1+n(2/n(n+1))+1
Question 2. Runtime analysis [5 marks]
Analyse the running time of of the following function, in terms of its input length, using the same structure we did in lecture.
You should clearly state how many steps each line of code takes. For each loop in the function, include the number of iterations, and number of steps per iteration.
Lastly, provide the total steps as an exact step count (e.g., n2 +2n +4) and then a Theta expression (e.g., Θ(n2 )) (note: you do not need to provide any formal proof or justification for translating the exact count to its associated Theta expression, similar to what we did in lecture).
def f4(n: int) -> None:
i = 0
while i < n: # Loop 1
for j in range(10): # Loop 2
print(j)
i = i + 4
Question 3. [4 marks]
Consider the following statement:
’a, b ∈ R+, a ≥ b ∆ an ∈ Ω(bn )
a. Rewrite the above statement, but with the definition of Omega expanded.
b. Prove the above statement without using any additional theorems about Omega. (Hint: your proof body should be quite short.)