Data Structures and Algorithms
For an array of n elements, what is the time complexity of comparing every pair of distinct elements exactly once (a double loop that compares element i with every element after it, advancing i one step at a time)?
- AO(n)
- BO(n log n)
- CO(n²)
Show answer and explanation
Answer: C. O(n²)
The number of pairs compared is (n−1) + (n−2) + … + 1 = n(n−1)/2: 45 for n = 10 and 499,500 for n = 1000. Big-O notation only describes how the count grows as n gets large, so the factor of 1/2 and the lower-order term are dropped, giving O(n²). Doubling n roughly quadruples the count. O(n) is the complexity of looking at each element once, and O(n log n) is that of algorithms such as merge sort that repeatedly split the data in half.
- A. Looking at each element once would be O(n), but here each element is compared with all of the remaining ones.
- B. This is the complexity of algorithms such as merge sort that repeatedly halve the data, which is smaller than comparing all pairs.
- C. Correct. There are n(n−1)/2 comparisons, which grows in proportion to n².