Does an array contain a repeated value? Write DuplicateCheck with three methods that answer the question and count their basic steps:
byPairs— compare every pair (count the comparisons; stop at the first duplicate);bySorting— sort a copy, then compare neighbours (count the neighbour comparisons);byHashing— add each value to aHashSetand stop whenaddreturnsfalse(count the set operations).
Input: n d. Build a[i] = 2i + 1; if 0 < d < n, set a[d] = a[0] so that position d repeats the first value (d = −1 means no duplicate).
For the input
1000 -1
the program prints
pairs: false after 499500 comparisons
sorting: false after 999 neighbour comparisons (plus the sort)
hashing: false after 1000 set operations
All three agree: true
Worst case for pairs with n = 1000: 499500