Operation Costs and Choosing by Workload

DynamicArray and SortedArray both store their elements in a backing array and keep a size counter. DynamicArray appends each new element at the end, in arrival order. SortedArray keeps its elements in sorted order at all times. Assume the backing array always has spare room, so it never has to grow. Both support these operations, and $n$ is the number of elements stored:

get(i) returns the element at index i.
contains(value) reports whether value is stored.
add(value) stores a new element.
remove(value) deletes the first occurrence of value and keeps the remaining elements in order, with no gap.

Exercise

Without looking at the code of either class, give the worst-case Big-Oh of each operation, with a one-line reason.

Operation	`DynamicArray`	`SortedArray`
`get`
`contains`
`add`
`remove`

Solution

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

get reads slot i of the backing array directly in both. contains must scan an unsorted array from the front, but can binary search a sorted one. add appends at the end in DynamicArray. In SortedArray it has to find where the value belongs, then shift up to $n$ elements to open a gap there, and the shifting costs more than the search. remove has to find the element and then shift everything after it left to close the gap. The shifting is $O (n)$ in both, no matter how fast the search is.

Solution

Roster A should be a SortedArray. The adds all happen once, at the start, and every lookup after that is $O (lo g n)$ instead of $O (n)$ .

Roster B should be a DynamicArray. Making every add $O (n)$ to speed up a search we rarely run is not worth it. Adds stay $O (1)$ and the occasional search costs $O (n)$ .

Removal is $O (n)$ in both structures, so it does not affect the choice.

Solution

One search costs the sort plus the binary search, $O (n lo g n) + O (lo g n) = O (n lo g n)$ . A plain linear scan of the unsorted array is $O (n)$ , so sorting for a single search is worse than not sorting at all.

The plan is faster than linear scans only when one sort is shared by many searches with no adds or removes in between. Then the $O (n lo g n)$ is paid once and each later search is $O (lo g n)$ .

Solution

Strategy	Big-Oh
1	$O (n^{2})$
2	$O (n^{2})$
3	$O (n)$
4	$O (n)$

Strategy 1 does an $O (n)$ scan for each of $n$ candidates. Strategy 2 is dominated by the $O (n^{2})$ selection sort; the final scan is a lower-order term. Strategy 3 is one pass over the array plus constant work. Strategy 4 is two sequential passes, $n + n$ , which is $O (n)$ .