Two Loops, Still Linear

Here is a method that searches for a target in two arrays, one after the other:

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;
}

Suppose both arrays have length $n$. How much work does this do, and what is its Big-Oh?

We have two loops, one after the other. Each is a linear search: a constant amount of work per element, repeated over $n$ elements. In the worst case the target is in neither array, so we scan both all the way through. That is about $n$ steps for the first loop and $n$ for the second, roughly $2n$ in total.

And $2n$ is $O(n)$. The factor of $2$ is a coefficient, and we suppress coefficients. When loops run one after another, their work adds. Running a linear scan twice, or three times, or any constant number of times, is still linear.

I set both arrays to length $n$ to keep the arithmetic simple. If they have sizes $m$ and $k$, the work is $O(m+k)$. The work is still linear. It is just that what adds is $m$ and $k$ rather than $n$ and $n$.