Exercise III

Consider the following program

public boolean contains (int[] a, int[] b, int target) {
  for (int i = 0; i < a.length; i++) {
    if (a[i] == target) {
      return true;
    }
  }

  for (int i = 0; i < b.length; i++) {
    if (b[i] == target) {
      return true;
    }
  }

  return false; 
}

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

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

Solution

The answer is the same as before, $O(n)$. The reason is that the worst-case number of operations performed (in an unsuccessful search) is twice that of the program in the previous exercise. This extra factor of 2 contributes only to the leading constant in the running time and it will be suppressed in Big Oh notation.