Reasoning About Operations Without the Code

In the previous section, we figured out that indexOfMin is $O (n)$ without looking at its code. We worked out the Big-Oh from what it has to do. indexOfMin has to find the smallest element, and the only way to do that is to look at every element, so it is $O (n)$ .

This “reasoning without the code” approach is a skill you will use often. Once you know what an operation does and how the data is organized, you can work out the cost without an implementation in front of you.

Let’s do that for the two structures we built, DynamicArray and SortedArray. Without looking at the code of either structure, reason about what each operation must do, and then determine the Big-Oh of each operation.

Operation	`DynamicArray`	`SortedArray`
`get(i)`	$O (1)$	$O (1)$
`contains` / `indexOf`	$O (n)$	$O (lo g n)$
`add`	$O (1)$	$O (n)$
`remove`	$O (n)$	$O (n)$

To get the element at index i, either structure jumps straight to that slot of the backing array. Finding the slot takes a fixed amount of arithmetic regardless of how big the array is, so reading by index is $O (1)$ for both.

Searching is where the two differ. DynamicArray implements linear search, which is $O (n)$ . SortedArray implements binary search, which is $O (lo g n)$ .

With add, DynamicArray puts the new element at the end and increments the size, which is $O (1)$ . SortedArray cannot do that, because the new element rarely belongs at the end. It has to find the position where the new element belongs (a binary search, $O (lo g n)$ ) and then shift every larger element over by one to open a gap (up to $n$ shifts, $O (n)$ ). The shifting dominates, so adding to a SortedArray is $O (n)$ .

What about grow()?

Both structures have a grow() method that is called when the backing array fills up. grow() copies every element into a larger array, which is $O (n)$ . For SortedArray, this has no effect on the Big-Oh of add, because add is already $O (n)$ . How about DynamicArray?

Assuming the backing array still has an unused slot, DynamicArray.add is $O (1)$ . But when the backing array fills up, add calls grow() so it becomes an $O (n)$ operation. It turns out that, averaged over many adds, the amortized cost still comes to $O (1)$ per add. We will cover amortized analysis in a later chapter.

We worked out the Big-Oh of remove earlier in this chapter. It finds the target and then shifts every element after it down by one index. That shifting dominates whatever the search cost is, so remove is $O (n)$ for both.

Notice the trade-off between the two structures. SortedArray gives us a much faster search, $O (lo g n)$ instead of $O (n)$ . In exchange, its add is much slower, $O (n)$ instead of $O (1)$ . This makes sense: binary search is what makes the search fast. It works only when the elements are sorted. Keeping them sorted on every insertion is what makes the add expensive.