Question 8 of 8: Algorithm Design and Sorting — Deduplicating a Large Array

Question 8: Algorithm Design and Sorting — Deduplicating a Large Array (20 marks)

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 containing duplicates, and two candidate dedupe strategies: (1) scan $A$ once, copying each element into $B$ only if $B$ does not already contain it; (2) Quicksort $A$ first, then apply the same scan-and-copy rule.

Find. Which method is faster for large $n$, with justification (not a benchmark on a specific machine, but an asymptotic argument).

Approach. Count worst-case comparisons for each method as a function of $n$ and the number of duplicates, then compare growth rates; confirm the argument by counting actual comparisons on the same synthetic data for both methods at increasing $n$.

1. Analyze Method 1 without sorting. For each of the $n$ elements of $A$, checking "does it already exist in $B$" is a linear scan of $B$, whose length grows as unique elements accumulate. In the worst case (all elements distinct, so $B$ grows to length $n$), the total number of comparisons is $$0+1+2+\cdots+(n-1) = \frac{n(n-1)}{2} = O(n^2)$$ Even with many duplicates the bound stays $O(n^2)$ in the worst case, since an adversarial input can still front-load $B$ with $\Theta(n)$ distinct values before any duplicate appears.
2. Analyze Method 2 with a Quicksort pre-pass. Quicksort's average-case running time is $O(n\log n)$ (its worst case is $O(n^2)$ only for an adversarial pivot choice on already-sorted or reverse data, which "an array of random integers" does not present). After sorting, every duplicate is adjacent to its equal neighbours, so the scan-and-copy becomes a single linear pass — compare each element only to the previous one, an $O(n)$ operation, not $O(n)$ comparisons against a growing $B$. $$T_2(n) = \underbrace{O(n\log n)}_{\text{Quicksort}} + \underbrace{O(n)}_{\text{one linear scan}} = O(n\log n)$$
3. Compare growth rates. Since $O(n\log n)$ is strictly smaller than $O(n^2)$ for all sufficiently large $n$ (formally, $\lim_{n\to\infty} \frac{n\log n}{n^2} = 0$), Method 2 is asymptotically faster whenever $n$ is "large," which is exactly the condition the question poses — even though Method 2 does strictly more total work per element for small $n$ (sorting overhead that a tiny array does not need to pay back). $$\boxed{\text{Method 2 (Quicksort, then one linear scan) is faster for large } n}$$
4. Confirm empirically by counting comparisons. Running both methods on the same randomly generated arrays (with many repeated values, matching "the array may contain duplicate integers") and counting every comparison performed shows the predicted crossover: the two methods are close at $n=200$, but Method 1's comparison count grows far faster than Method 2's as $n$ increases to 2,000 and 20,000.

   n =    200   naive ~   1,961 comparisons   sort+scan ~   1,894 comparisons  (1.0x)
   n =  2,000   naive ~ 191,088 comparisons   sort+scan ~  28,392 comparisons  (6.7x)
   n = 20,000   naive ~19,062,178 comparisons  sort+scan ~ 374,320 comparisons (50.9x)

   The ratio itself grows with $n$, which is the signature of two different polynomial/log-linear growth rates rather than a fixed constant-factor difference — confirming the $O(n^2)$ vs $O(n\log n)$ analysis above rather than just an implementation-specific speed difference.