Two programmers, Ada and Charles, write different Python programs to calculate the sum of the squares of the first $n\,$ positive integers: $∑i=1ni2\sum_{i=1}^{n} i^2$ .

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)$ , meaning they are equally efficient as $n$ grows large.

Program Ada has a worst-case time complexity of $O(n^2)$ due to the exponentiation i ** 2, while Program Charles has a worst-case time complexity of $O (1)$ , making Program Charles more efficient.

Program Ada has a worst-case time complexity of $O (n)$ and Program Charles has a worst-case time complexity of $O (1)$ , making Program Charles more efficient for large values of $n$ .

Program Ada has a worst-case time complexity of $O (1)$ because the loop bounds are known, while Program Charles has a worst-case time complexity of $O (n)$ due to the multi-variable multiplication.

Two programmers, Ada and Charles, write different Python programs to calculate the sum of the squares of the first $n\,$ positive integers: $∑i=1ni2\sum_{i=1}^{n} i^2$ .

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)$ , meaning they are equally efficient as $n$ grows large.

Program Ada has a worst-case time complexity of $O(n^2)$ due to the exponentiation i ** 2, while Program Charles has a worst-case time complexity of $O (1)$ , making Program Charles more efficient.

Program Ada has a worst-case time complexity of $O (n)$ and Program Charles has a worst-case time complexity of $O (1)$ , making Program Charles more efficient for large values of $n$ .

Program Ada has a worst-case time complexity of $O (1)$ because the loop bounds are known, while Program Charles has a worst-case time complexity of $O (n)$ due to the multi-variable multiplication.

Efficiency of algorithms

Question 2

Markscheme

Efficiency of algorithms

Question 2

Markscheme

Efficiency of algorithms

Question 2

Efficiency of algorithms Questions

Efficiency of algorithms

Question 2

Efficiency of algorithms Questions