Exercise IV

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

Consider the following program

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

  return false; 
}

Exercise What is the asymptotic running time of the code above for checking for a common element, as a function of the array lengths nn? Assume both arrays are of the same size.

A) O(n2)\Omicron(n^2)
B) O(n!)\Omicron(n!)
C) O(n)\Omicron(n)

Solution

The answer is O(n2)\Omicron(n^2). The program performs a constant number of operations for each loop iteration (for each choice of the indices i and j). However, for each iteration of the outer for loop, the code performs nn iterations of the inner for-loop. This gives n×n=n2n \times n = n^2 iterations in all.