Nested-Loop Pair Count with Initialization Bug
A student writes the following pseudocode to count pairs (i, j) with i < j and a[i] + a[j] = k:
count ← 1 for i from 0 to n − 2 for j from i + 1 to n − 1 if a[i] + a[j] = k count ← count + 1
The student runs it on a = [2, 7, 4, 5, 3, 1], n = 6, k = 9, and reports the output 3. The student claims this counts every pair whose values sum to 9 and that the algorithm is efficient because the inner loop starts after i. A classmate says the initial value is wrong and that the nested loops are not as efficient as claimed. The teacher asks the student to trace the code, check the output, and justify the running time.
1. Trace the pseudocode for the given array and k. List every pair that satisfies the condition, state the final output, and identify the defect.
Read the worked answer
Trace: i=0, j=1: a[0]+a[1]=2+7=9, count 1→2. i=0, j=2: 6; j=3:7; j=4:5; j=5:3. i=1, j=2:11; j=3:12; j=4:10; j=5:8. i=2, j=3:4+5=9, count 2→3. i=2, j=4:7; j=5:5. i=3, j=4:8; j=5:6. i=4, j=5:4. Only (2,7) and (4,5) satisfy. The correct output is 2, but the code prints 3 because count starts at 1. The defect is the initialization; the loop bounds and comparison are otherwise consistent with i<j.
2. The student says the algorithm is O(n) because the inner loop runs only for later elements. Evaluate this claim and give the exact number of comparisons for n=6 and in general.
Read the worked answer
For each i, the inner loop runs n−1−i times. The total is (n−1)+(n−2)+...+1 = n(n−1)/2. For n=6 that is 15 comparisons, not 6. The growth is quadratic, O(n^2), because doubling n roughly quadruples the work. The inner loop starting later does not make it linear; it only halves the constant factor. The student's O(n) claim is therefore false.
3. Propose an O(n log n) or O(n) method for the same task and state one assumption it needs.
Read the worked answer
Use a hash map from value to number of times it has been seen. Scan the array once; for each a[j], add the number of previously seen elements equal to k−a[j] to the count, then insert a[j]. This counts each i<j pair once and runs in O(n) average time, using O(n) extra space. It assumes hash operations are average O(1) and that the array values can be hashed exactly (integers here). A sort-and-two-pointer alternative is O(n log n) time and O(1) extra space if the array may be sorted, but it must handle duplicate values carefully.