Two python programs, Program P and Program Q, are designed to calculate the total number of unique handshakes that occur when each of the N N\,N people in a room shakes hands with everyone else exactly once.
Program P
n = int(input("Enter number of people: "))
handshakes = 0
for i in range(1, n):
for j in range(i + 1, n + 1):
handshakes = handshakes + 1
print(handshakes)
Program Q
n = int(input("Enter number of people: "))
handshakes = (n * (n - 1)) // 2
print(handshakes)
Select the option that correctly describes and compares the time efficiency of these two programs.
Program P has a time complexity of O(N)O(N)O(N) and is more efficient than Program Q, which has a time complexity of O(1)O(1)O(1).
Program Q has a time complexity of O(1)O(1)O(1) and is more efficient than Program P, which has a time complexity of O(N2)O(N^2)O(N2).
Both programs have a time complexity of O(N2)O(N^2)O(N2) and are equally efficient.
Program Q has a time complexity of O(N)O(N)O(N) and is more efficient than Program P, which has a time complexity of O(N2)O(N^2)O(N2).
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.