Lesson 7.4 · Answer it
Pair sum cases
4 marksYou mark it yourself against the marking points
This function returns whether any two values at different positions in a list add up to total. It compares pairs, and returns as soon as it finds one that works.
def has_pair(values, total):
for i in range(len(values)):
for j in range(i + 1, len(values)):
if values[i] + values[j] == total:
return True
return False
public static boolean hasPair(int[] values, int total) {
for (int i = 0; i < values.length; i++) {
for (int j = i + 1; j < values.length; j++) {
if (values[i] + values[j] == total) {
return true;
}
}
}
return false;
}
The list holds n values, where n is at least 2. Count one comparison each time the if is checked.
(a) Describe the input that gives the best case, and state how many comparisons it makes. [2]
(b) State how many comparisons the worst case makes when n is 5. [1]
(c) State the Big O complexity of the worst case. [1]
[4]