Two programmers, Ada and Charles, write different Python programs to calculate the sum of the squares of the first n n\,n positive integers: ∑i=1ni2\sum_{i=1}^{n} i^2∑i=1ni2.
Program Ada
n = int(input())
total = 0
for i in range(1, n + 1):
total += i ** 2
print(total)
Program Charles
n = int(input())
total = (n * (n + 1) * (2 * n + 1)) // 6
print(total)
Which of the following statements correctly describes and compares the worst-case time complexities of these programs?
Both programs have a worst-case time complexity of O(n)O(n)O(n), meaning they are equally efficient as nnn grows large.
Program Ada has a worst-case time complexity of O(n2)O(n^2)O(n2) due to the exponentiation i ** 2, while Program Charles has a worst-case time complexity of O(1)O(1)O(1), making Program Charles more efficient.
Program Ada has a worst-case time complexity of O(n)O(n)O(n) and Program Charles has a worst-case time complexity of O(1)O(1)O(1), making Program Charles more efficient for large values of nnn.
Program Ada has a worst-case time complexity of O(1)O(1)O(1) because the loop bounds are known, while Program Charles has a worst-case time complexity of O(n)O(n)O(n) due to the multi-variable multiplication.
Practise AQA GCSE Computer Science Efficiency of algorithms with exam-style questions for GCSE Computer Science. 15 questions, matched to the AQA GCSE Computer Science (8525) specification and written in Paper 1 and Paper 2 style. Every question includes a full worked solution and mark scheme, so you can see where marks are awarded rather than just whether you got the answer right.