Demo: turning an O(n²) solution into O(n)

Written Explanation

Step 1: the obvious solution

static boolean nested(int[] a) {
    for (int i = 0; i < a.length; i++)
        for (int j = i + 1; j < a.length; j++)
            if (a[i] == a[j]) return true;
    return false;
}

Compare every pair once (j starts at i + 1, so each pair is checked only once and no element is compared with itself). When there are no duplicates, the worst case, the inner comparison runs n × (n - 1) / 2 times. For 100,000 numbers that is 4,999,950,000. The time is O(n²) and the extra space is O(1). Correct, simple, and slow on large input.

A quick check of correctness: nested(new int[]{3, 1, 4, 1}) printed true.

Step 2: measure it

Timing needs care (BEG-030): one run includes warm-up and noise, so the harness below runs each method three times and keeps the fastest. The input is the worst case: the values 0, 1, ..., n - 1, all different, so the methods must look at everything.

interface Check { boolean run(int[] a); }

static long micros(Check c, int[] a) {
    long best = Long.MAX_VALUE;
    for (int r = 0; r < 3; r++) {
        long t = System.nanoTime();
        c.run(a);
        best = Math.min(best, System.nanoTime() - t);
    }
    return best / 1_000;                 // microseconds
}

Passing a method as a value, micros(L06::nested, a), uses a method reference (BEG-035).

Step 3: the planned mistake

A first idea: keep a list of the numbers seen so far and use contains, so there is only one loop:

static boolean withList(int[] a) {
    List<Integer> seen = new ArrayList<>();
    for (int x : a) {
        if (seen.contains(x)) return true;    // looks like O(1)
        seen.add(x);
    }
    return false;
}

It looks like O(n): one loop. But seen.contains(x) scans the list, which has up to i elements at iteration i, so the total is up to 0 + 1 + ... + (n - 1), which is O(n²) again. L03 called this a hidden loop: the ArrayList documentation puts contains among the operations that run in linear time. The code is shorter and the complexity is the same.

Step 4: the fix

static boolean withSet(int[] a) {
    Set<Integer> seen = new HashSet<>();
    for (int x : a) {
        if (!seen.add(x)) return true;        // add returns false if x was already present
    }
    return false;
}

HashSet.add returns false when the element is already in the set, so one call both checks and inserts. The HashSet documentation promises constant-time basic operations, assuming a hash function that disperses the elements well, which Integer does. One loop with a constant-time step: O(n) time on average. The set can hold up to n numbers: O(n) space.

Step 5: time all three

Output of my run on JDK 21 (a Windows laptop; best of three runs; microseconds), all inputs without duplicates:

At 100,000 elements: nested loops about 1.3 seconds, the list version about 4.9 seconds, the HashSet version about 5 milliseconds. The set was roughly 250 times faster than the nested loops and roughly 900 times faster than the list version. The set also ran a million elements in about 78 milliseconds in the same session (77,850 microseconds), something the other two could not do in reasonable time (the nested loops would need about 500 billion comparisons).

Read the table for growth, not for exact values. From 10,000 to 100,000, n grows ten times and the nested loop's time grows about 109 times (roughly the 100 times that n² predicts). The list version grows about 113 times. The set grows about 4 times, a little below the ten that O(n) predicts, which is plausible for warm-up and noise at such small times. At 1,000 elements the three are close together; the difference only becomes decisive as n grows. The list version being slower than the nested loops is plausible given that contains compares boxed Integer objects with equals and the list also does add calls; I did not profile it to confirm.

Step 6: state the trade

withList is the worst of both worlds: it uses O(n) memory and gets no speed-up. withSet pays O(n) memory for a large time gain. If memory is very tight, or n is tiny, nested loops are still a legitimate choice.

The same pattern for "pair with a given sum"

Problem: does the array have two different positions whose values add to target?

static boolean pairNested(int[] a, int target) {          // O(n^2) time, O(1) space
    for (int i = 0; i < a.length; i++)
        for (int j = i + 1; j < a.length; j++)
            if (a[i] + a[j] == target) return true;
    return false;
}

static boolean pairSet(int[] a, int target) {             // O(n) average time, O(n) space
    Set<Integer> seen = new HashSet<>();
    for (int x : a) {
        if (seen.contains(target - x)) return true;       // the partner was seen earlier
        seen.add(x);
    }
    return false;
}

For {2, 7, 11, 15} with target 9, both returned true (2 + 7); pairSet with target 100 returned false. The idea: for each x, the number we need is target - x; a set answers "have I seen it?" in constant time. Checking contains before add ensures an element is not paired with itself.