Why We Drop Lower Terms

Recall the implementation of remove in DynamicArray and SortedArray:

public boolean remove(T value) {
  int i = indexOf(value);     // linear or binary search?
  if (i == -1) {
    return false;             // not here
  }
  for (int j = i; j < size - 1; j++) {
    arr[j] = arr[j + 1];      // shift the rest one slot left
  }
  size--;
  arr[size] = null;           // clear the vacated slot
  return true;
}

This method does two things. First it finds the element, and then it shifts everything after it one slot to the left. Let’s analyze each part.

The cost of indexOf is where the two implementations differ. The DynamicArray version of indexOf uses linear search, which is $O (n)$ . The SortedArray version uses binary search, which is $O (lo g n)$ .

The shifting is the same in both. The loop copies every element after position i one slot left, so it runs size - 1 - i times. In the worst case we remove the first element, i is $0$ , and the loop runs $n - 1$ times. So the shifting is $O (n)$ in both implementations.

Putting the two parts together:

DynamicArray.remove does $O (n)$ for the linear search plus $O (n)$ for the shifting, so $O (n) + O (n) = O (2 n)$ .
SortedArray.remove does $O (lo g n)$ for the binary search plus $O (n)$ for the shifting, so $O (lo g n) + O (n) = O (n + lo g n)$ .

Suppressing the coefficient turns $2 n$ into $n$ , so DynamicArray.remove is $O (n)$ , and we justified that in the previous section.

Dropping the lower term turns $n + lo g n$ into $n$ , so SortedArray.remove is also $O (n)$ . Why are we allowed to drop the lower term? Let’s look at some numbers. Assume a processor that does a million instructions per second, and see how long $n$ and $lo g n$ take. The table also shows $n^{2}$ for comparison:

size	$n$	$lo g_{2} n$	$n^{2}$
$n = 10$	$< 1 sec$	$< 1 sec$	$< 1 sec$
$n = 1000$	$< 1 sec$	$< 1 sec$	$1 sec$
$n = 1000000$	$1 sec$	$< 1 sec$	$12 days$
$n = 1000000000$	$\sim 17 min$	$< 1 sec$	$\sim 31, 700 years$

Look at the row for a million. The $n$ column costs a second and the $lo g n$ column costs less than a second. Adding the two together still costs about a second. The $lo g n$ term does not add anything you could measure. At a billion, the $n$ column costs about 17 minutes and the $lo g n$ column still costs less than a second. The larger $n$ gets, the less the $lo g n$ term matters. That is why we drop it. Work of $α n + β lo g n$ steps is $O (n)$ asymptotically, because the $lo g n$ term is negligible next to the $n$ term as $n$ grows.

The same argument works for any pair of terms where one grows faster. If the work is $α n^{2} + β n + γ lo g n + δ$ , look at the million row again: the $n^{2}$ term costs 12 days and the $n$ and $lo g n$ terms together cost about a second. Twelve days plus a second is twelve days. So we drop the lower terms and say the work is $O (n^{2})$ .

This is what the second step is for. On large inputs the dominant term is almost all of the cost, so the terms we drop were not contributing much anyway.