Big-Oh from Loop Structure

For each method below, give the Big-Oh of its worst-case running time. Unless the question says otherwise, every array has length $n$ .

Exercise

What is the Big-Oh of countMatches?

public static int countMatches(int[] a, int[] b, int target) {
  int count = 0;
  for (int i = 0; i < a.length; i++) {
    if (a[i] == target) {
      count++;
    }
  }
  for (int j = 0; j < b.length; j++) {
    if (b[j] == target) {
      count++;
    }
  }
  return count;
}

Solution

$O (n)$ . The two loops run one after the other, so their work adds: $n + n = 2 n$ , and the $2$ is a suppressed coefficient.

Exercise

What is the Big-Oh of countPairSums?

public static int countPairSums(int[] a, int[] b, int target) {
  int count = 0;
  for (int i = 0; i < a.length; i++) {
    for (int j = 0; j < b.length; j++) {
      if (a[i] + b[j] == target) {
        count++;
      }
    }
  }
  return count;
}

Solution

$O (n^{2})$ . The loops are nested, so their work multiplies. The inner comparison runs once for every pair (i, j), which is $n \times n = n^{2}$ times.

Exercise

Exactly how many times does the comparison a[i] > a[j] run in countInversions, and what is the Big-Oh of the method?

public static int countInversions(int[] a) {
  int count = 0;
  for (int i = 0; i < a.length; i++) {
    for (int j = i + 1; j < a.length; j++) {
      if (a[i] > a[j]) {
        count++;
      }
    }
  }
  return count;
}

Solution

The comparison runs $(n - 1) + (n - 2) + \dots + 1 + 0 = \frac{n ( n - 1 )}{2}$ times. That is $\frac{1}{2} n^{2} - \frac{1}{2} n$ . Suppress the coefficients, drop the lower-order term, and the method is $O (n^{2})$ .

Exercise

countDigits takes a single positive integer. What does $n$ stand for here, and what is the Big-Oh of the method?

public static int countDigits(int num) {
  int count = 0;
  while (num > 0) {
    num = num / 10;
    count++;
  }
  return count;
}

Solution

There is no array. The work grows with the value of num, so $n$ is that value. Each pass divides num by $10$ , and dividing by a constant on every pass means the loop runs a logarithmic number of times. The method is $O (lo g n)$ .

Exercise

allPresent returns true when every element of a also appears in b. contains is a linear search over b. What is the Big-Oh of allPresent?

public static boolean contains(int[] b, int value) {
  for (int j = 0; j < b.length; j++) {
    if (b[j] == value) {
      return true;
    }
  }
  return false;
}

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

Solution

$O (n^{2})$ . The body of allPresent has one loop, but that loop’s body is not constant work: it calls contains, which is $O (n)$ . An $O (n)$ call made $n$ times is $O (n^{2})$ .