Two algorithms both calculate the sum of the whole numbers from 1 to n.
Algorithm A
n ← STRING_TO_INT(USERINPUT)
total ← 0
FOR i ← 1 TO n
total ← total + i
ENDFOR
OUTPUT totalAlgorithm B
n ← STRING_TO_INT(USERINPUT)
total ← (n * (n + 1)) DIV 2
OUTPUT total(a) State the output of both algorithms when the user enters 10. [1]
(b) Explain which algorithm is more efficient in terms of time. [2]
(c) A sorted list contains 1000 items. State the maximum number of items that would need to be checked against the search value to find an item (or show it is not there) using:
(i) a linear search [1]
(ii) a binary search. [1]
- (a) 55 (for both); accept 55 stated once as the output of both(1)
- (b) Algorithm B (no mark for B on its own) — it carries out the same (fixed) number of steps / one calculation whatever the value of n; allow B does not use a loop / iteration so does not depend on n(1)
- (b) Algorithm A's loop repeats n times, so the number of steps / time taken increases as n increases (allow for large n A takes much longer). Big-O notation not required but accept B is O(1) and A is O(n) with explanation(1)
- (c)(i) 1000(1)
- (c)(ii) 10(1)
- Answer: (a) 55 (b) B: fixed number of operations; A loops n times (c)(i) 1000 (ii) 10
- Examiner tip: 'B is shorter' is not an efficiency argument. Talk about how the number of steps changes as n gets bigger.