Problem: Analyze Nested Loops

Scenario 1: The Sequential Loop

public void printTwice(int[] arr) {
    for (int x : arr) System.out.println(x);
    for (int x : arr) System.out.println(x);
}

Analysis:

• Loop 1: $O(n)$
• Loop 2: $O(n)$
• Total: $O(2n) \rightarrow \mathbf{O(n)}$ (Constants are dropped).

Scenario 2: The Nested Loop

public void printPairs(int[] arr) {
    for (int i = 0; i < arr.length; i++) {
        for (int j = 0; j < arr.length; j++) {
            System.out.println(arr[i] + "," + arr[j]);
        }
    }
}

Analysis:

• For every iteration of the outer loop ($n$), the inner loop runs $n$ times.
• Total: $n \times n = \mathbf{O(n^2)}$.

Scenario 3: The Optimized Nested Loop

public void printUniquePairs(int[] arr) {
    for (int i = 0; i < arr.length; i++) {
        for (int j = i + 1; j < arr.length; j++) {
            System.out.println(arr[i] + "," + arr[j]);
        }
    }
}

Analysis:

• The inner loop runs $n-1, n-2... 1$ times.
• Sum is $\frac{n(n-1)}{2} = 0.5n^2 - 0.5n$.
• Total: $\mathbf{O(n^2)}$ (Only the highest order term matters).