Skip to content
ExamSpine

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]

Report a problem with this page