Exercise V

Consider the following program

public boolean hasDuplicates (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; 
}

Exercise What is the asymptotic running time of the code above for checking for duplicates, as a function of the array lengths $n$?

A) $O(n^2)$
B) $O(\lg n)$
C) $O(n)$

Solution

The answer is the same as before $O(n^2)$. The running time is proportional to the number of iterations of the double for loop (with a constant number of operations per iteration).

So how many iterations are there? The answer is roughly $n^2$:

  • One way to see this is to remember that this piece of code does roughly half the work of the previous one (since the inner for loop starts at j = i + 1 rather than j = 0).

  • A second way is to observe that when i = 0 the inner loop runs $(n - 1)$ times. When i = 1 the inner loop runs $(n-2)$ times. $\dots$ When i = n - 1, the inner loop runs $0$ times. So the total number of times the inner loop runs (which is where the program does its most work) is:

$$ (n-1) + (n-2) + \dots + 0 = \frac{n(n-1)}{2} \in O(n^2) $$