Two algorithms, Algorithm Alpha and Algorithm Beta, are designed to compute the sum of the cubes of the first n n\,n positive integers, ∑i=1ni3\sum_{i=1}^{n} i^3∑i=1ni3.
Algorithm Alpha
n = int(input("Enter a positive integer: "))
total = 0
for i in range(1, n + 1):
total += i**3
print(total)
Algorithm Beta
n = int(input("Enter a positive integer: "))
total = (n * (n + 1) // 2) ** 2
print(total)
Which statement correctly compares the efficiency of the two algorithms?
Both algorithms have a time complexity of O(n3)O(n^3)O(n3) because they calculate the sum of cubes, meaning they are equally efficient.
Algorithm Alpha has a time complexity of O(n)O(n)O(n) due to the loop, while Algorithm Beta has a time complexity of O(1)O(1)O(1), making Algorithm Beta more efficient for large values of nnn.
Algorithm Alpha has a time complexity of O(1)O(1)O(1) as it runs in a single execution block, while Algorithm Beta has a time complexity of O(n)O(n)O(n) due to the multi-step algebraic operations, making Algorithm Alpha more efficient.
Both algorithms have a time complexity of O(1)O(1)O(1) because modern processors can compute both the loop and the algebraic formula in a negligible amount of time.
15 exam-style questions on AQA GCSE Computer Science Efficiency of algorithms. Each one has a worked solution and a mark scheme showing where the marks go.