Question 9 of 9: Algorithm Design and Sorting — Removing Duplicates

Question 9: Algorithm Design and Sorting — Removing Duplicates (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 algorithms for building a duplicate-free array $B$: (1) scan $A$ once, checking each element against everything already placed in $B$ before appending it; (2) quicksort $A$ first (average case $O(n\log n)$), then perform the same "check-then-append" scan, now against an array that is sorted.

Find. Which method is asymptotically faster for large $n$, with justification.

Approach. Analyze the cost of the "does this item already exist in B" check under each method: against an unsorted, growing $B$ it is an $O(|B|)$ linear scan every time, but against a sorted array built from sorted input, duplicates of the same value are always adjacent, so the check collapses to a single $O(1)$ comparison against the last element appended to $B$.

1. Cost of Method 1 (no sort). In the worst case (all distinct, or duplicates arriving late) the $k$-th element is checked against up to $k-1$ existing entries of $B$: $$T_1(n) = \sum_{k=1}^n O(k) = O(n^2)$$ This is a plain member scan repeated $n$ times — nothing about Method 1 gets cheaper as $n$ grows.
2. Cost of Method 2 (sort, then scan). Quicksort costs $O(n\log n)$ on average. Once $A$ is sorted, every occurrence of a given value is contiguous, so "does this equal the previous distinct value kept" is a single comparison against $B$'s last entry — no scan of $B$ at all is needed: $$T_2(n) = \underbrace{O(n\log n)}_{\text{quicksort}} + \underbrace{O(n)}_{\text{one-pass dedup scan}} = O(n\log n)$$

   /* Method 1: O(n^2) worst case */
   int exists(const int *b, int blen, int x)
   {
       int i;
       for (i = 0; i < blen; i++) if (b[i] == x) return 1;
       return 0;
   }
   int dedup_unsorted(const int *a, int n, int *b)
   {
       int blen = 0, i;
       for (i = 0; i < n; i++)
           if (!exists(b, blen, a[i])) b[blen++] = a[i];
       return blen;
   }
   
   /* Method 2: O(n log n) -- sort first, then a single linear scan */
   int dedup_via_sort(int *a, int n, int *b)   /* a[] is sorted in place first */
   {
       int blen = 0, i;
       /* quicksort(): the standard in-place Quicksort the question names
          (CLRS ch. 7).  Not reproduced here -- this question asks only which
          of the two methods is faster, not for the sort itself.  Average
          O(n log n); worst case O(n^2) on an adversarial pivot sequence. */
       quicksort(a, 0, n - 1);
       for (i = 0; i < n; i++)
           if (blen == 0 || b[blen - 1] != a[i]) /* O(1): only the last entry can match */
               b[blen++] = a[i];
       return blen;
   }

3. Compare the growth rates and confirm empirically. For large $n$, $O(n\log n)$ overtakes $O(n^2)$ — the ratio $n^2/(n\log n) = n/\log n \to \infty$. A Python re-implementation of both methods times them at $n=2000,4000,8000$ random integers. The absolute times depend on the machine and are quoted only to show the shape of each curve; the ratios are the reproducible part. On one run, Method 1 takes 4.5 ms, 18.3 ms, 73.5 ms — each doubling of $n$ multiplies the time by about 4 (4.1× then 4.0×), the $O(n^2)$ signature — while Method 2 takes 0.18 ms, 0.35 ms, 0.77 ms over the same inputs, each doubling multiplying the time by only about 2 (1.9× then 2.2×), the $O(n\log n)$ signature. $$\boxed{\text{Method 2 (sort, then scan) is faster for large } n:\ O(n\log n) \text{ vs. } O(n^2)}$$