Exercise III

  • Use Big-Oh notation to describe the asymptotic runtime of a program.

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) $\Omicron(n^2)$
B) $\Omicron(2n)$
C) $\Omicron(n)$

Solution

The answer is the same as before, $\Omicron(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.