Algorithm Design and Sorting: 25-Comp-A4 Program Design and Data Structures, May 2013, Q8

Question 8: Algorithm Design and Sorting

Question text not reproduced: the examination questions are © Engineers and Geoscientists BC. Open the official past paper (linked at the top of this page) to read the question, then follow the worked solution below.

Given. An unsorted array $A$ of $n$ integers, possibly with duplicates, $n$ large. Find. Which of the two proposed methods for building the duplicate-free array $B$ is asymptotically faster, and why.

Approach. Analyze the dominant cost of each method as a function of $n$: Method 1's cost is driven by how the "does it already exist in B?" check scales as $B$ grows; Method 2's cost is dominated by the sort, but a sorted array turns the existence check into a trivial adjacent comparison.

Method 1: linear existence check. For each of the $n$ elements of $A$, checking "does it already exist in $B$?" by scanning $B$ costs, in the worst case (few or no duplicates, so $B$ grows to nearly size $n$), up to $|B|$ comparisons. Summed over all $n$ insertions this is $$1+2+\cdots+(n-1) = \frac{n(n-1)}{2} = \boxed{O(n^2)}.$$
Method 2: sort, then a single dedup pass. Quicksort costs $O(n\log n)$ on average (its worst case, $O(n^2)$, only arises on already-sorted or adversarial pivot-selection inputs, and is avoided in practice with randomized or median-of-three pivot choice). Once $A$ is sorted, every duplicate of a value is adjacent to it, so a single linear scan comparing each element only to its immediate predecessor removes all duplicates in $O(n)$. Total: $$O(n\log n) + O(n) = \boxed{O(n\log n)}\ \text{(average case)}.$$
Compare for large $n$. Because $n\log n$ grows strictly slower than $n^2$ once $n$ is at all large, Method 2 wins asymptotically — and the crossover happens quickly: at $n=1000$, $n^2 \approx 5\times$ the operation count of $n\log n$ already, and the gap widens without bound as $n$ grows further.

Method	Dominant cost	Complexity
1: linear existence check while building B	up to $\|B\|$ comparisons per insertion	$O(n^2)$ worst case (few duplicates)
2: Quicksort, then adjacent-duplicate scan	the sort dominates; dedup pass is $O(n)$	$O(n\log n)$ average case
Winner for large $n$	$\boxed{\text{Method 2}}$ — $n\log n$ beats $n^2$ once $n$ is large

Concept & Theory

Topic. Trading a sort's $O(n\log n)$ up-front cost for a much cheaper downstream operation — here, deduplication.

Key relations. Quicksort: $O(n\log n)$ average, $O(n^2)$ worst case (mitigated by randomized pivots); a sorted array's duplicates are always adjacent, so removing them needs only $O(n)$ comparisons instead of an $O(n)$-per-item existence check against a growing unsorted collection.

Why this works. Method 1 pays an existence-check cost that grows with how much of $A$ has already been processed (up to $n$ comparisons for the last element in the worst case), giving the classic arithmetic-series $O(n^2)$ total; sorting first converts "does this value exist anywhere in what I've built so far?" into "does this value equal the one right before it?" — a fixed $O(1)$ check per element, so the post-sort work collapses to linear.

Common pitfall. Assuming Quicksort's worst case ($O(n^2)$, on an already-sorted or reverse-sorted array with a naive first-or-last-element pivot) can never happen in practice — a fully rigorous answer should note that using a randomized or median-of-three pivot avoids this, or that Method 2's worst case degrades to the same order as Method 1 (though still followed by a cheap $O(n)$ dedup, so it never gets asymptotically worse than Method 1). A second common error is using a hash set for the existence check in Method 1 and calling it $O(n)$ overall — the question specifies checking against array $B$ directly, which is what makes Method 1's cost quadratic.

Source. Cormen, Leiserson, Rivest & Stein, Introduction to Algorithms §7 (Quicksort and its average/worst-case analysis), §2.2 (asymptotic notation and the arithmetic-series bound behind $O(n^2)$ algorithms).

Question 8 of 8: Algorithm Design and Sorting

Question 8: Algorithm Design and Sorting