Linear vs. Binary Search, Side by Side

We have counted the number of comparisons each search makes. Linear search, in the worst case, touches every element, so about $n$ comparisons. Binary search, in the worst case, takes about $lo g n$ comparisons. Written next to each other, $n$ and $lo g n$ do not look very different. Let’s put numbers in for $n$ and see how they compare.

A concrete comparison

Suppose each comparison takes about $0.004$ milliseconds, and we always look at the worst case, where the target is absent. Here is how many comparisons each search makes:

elements ( $n$ )	linear search	binary search
1,000	~1,000 comparisons	~10 comparisons
1,000,000	~1,000,000 comparisons	~20 comparisons

Turn those comparison counts into time:

At $n = 1, 000$ : linear takes about $1, 000 \times 0.004 = 4$ milliseconds; binary takes about $10 \times 0.004 = 0.04$ milliseconds.
At $n = 1, 000, 000$ : linear takes about $1, 000, 000 \times 0.004 = 4, 000$ milliseconds, four whole seconds; binary takes about $20 \times 0.004 = 0.08$ milliseconds.

How each one grows

The individual numbers matter less than what happens to them when the array grows. The array grew by a factor of 1,000 here, from a thousand elements to a million. Look at what happened to each search.

Linear search’s work increases by that same factor of 1,000, from 4 ms to 4,000 ms. That proportional growth is why we call it linear search.
Binary search only doubled, from about 10 comparisons to about 20. That happens because every time you double $n$ , you need exactly one more halving to get back down to 1, so $lo g n$ goes up by one. Multiplying $n$ by 1,000 is close to doubling it ten times, since $2^{10}$ is 1,024. Ten doublings means ten extra comparisons.

Linear search’s cost is tied to the size of the input. Binary search’s cost is tied to how many times you have to double 1 to reach that size, which is a far smaller number. The gap is even bigger at larger sizes. At a billion elements, linear search takes about four million milliseconds, which is over an hour, and binary search finishes in about thirty comparisons, which is about 0.12 milliseconds.

Linear search on sorted data

Sorting helps even linear search a little. On a sorted array, a scan can stop the moment it passes where the target would be, so a search for an absent small value ends early. But the worst case is unchanged. Look for a value larger than everything present and you still iterate over all $n$ elements.

The task and the data have not changed. We are still looking for a target among the same $n$ elements in the same array. The only thing that changed is the order of the data. Once the array is sorted, we can use binary search, which finds the target much faster. Next we build a SortedArray class that keeps its elements in order, so binary search always applies to it.