Operation Costs Behind the Interface

Let’s figure out the time complexity of selectionSort when it is called on a DynamicArray and on a LinkedList. The code is the same in both cases, but the cost is not.

The interface guarantees that every List has a get. On a DynamicArray, get reads straight from the backing array. It is an $O(1)$ operation. On a LinkedList, get has to follow the links from the head, node by node, until it reaches the given position. It is an $O(n)$ operation.

Now look at where get is called in selectionSort. It is called inside the inner loop, on every pass:

for (int j = i + 1; j < list.size(); j++) {
  if (list.get(j).compareTo(list.get(minIndex)) < 0) {
    minIndex = j;
  }
}

Count the work for a DynamicArray. The outer loop runs about $n$ times. For each of those, the inner loop runs about $n$ times. Each pass of the inner loop calls get twice, and each get is $O(1)$. Multiply the outer loop, the inner loop, and the cost of get, and we get $n\times n\times O(1)$, which is $O(n^2)$. That is the cost we expect of selection sort.

Now count the same three factors for a LinkedList. The outer loop still runs about $n$ times. The inner loop still runs about $n$ times. The third factor is different. Each get is now $O(n)$. So the product is $n\times n\times O(n)$, which is $O(n^3)$.

So if we were to sort the same list of values, using the same selectionSort code, the LinkedList implementation would take longer than the DynamicArray implementation. Keep in mind this is not inherently a feature of a linked list. We can implement selection sort over a linked list in $O(n^2)$ time, but we need to keep track of the node we are currently at, instead of calling get each time. The point here is that the interface forces us to use get, and when the list is implemented as a linked list, get is expensive.

The interface hides the cost of the underlying implementation. List is a set of operations, a contract, described independently of any particular implementation.