Linear Search Versus Binary Search — A Visual Comparison

Because a picture is worth a thousand words

Linear Search

A linear search is the most basic search algorithm. It iterates a list sequentially from the first index to the last index. At each index it fetches the value at that location and checks if it is the value being searched.

Average search time for a linear search algorithm depends linearly on the size of the list being searched — hence the name linear search.

If the search execution time is T for a list with N items, a list of 2N elements would take time 2T, a list with 3N elements would take time 3T, and so on and so forth , all other conditions being the same.

Following is the graph of a list being searched using the linear search algorithm. Each sample size was searched just once to obtain the search time.

The x-axis represents the number of elements inside the list (List Size). The y-axis represents the time taken to finish the search (Search Time).

Linear Search: The list was searched only 1 time for each sample size

As we can see, the above graph is not a straight line. It is because the time taken to search a list depends on many factors that are not in our control, some of which are:

1. Memory allocation
2. CPU allocation
3. The position of item being searched in the list

Numbers of steps taken by a linear search algorithm varies based on where the searched item is in the list. If it is the first item in the list then linear search would find it in just a single step.

But if the item being searched does not exist in the list, or if it is the last item, linear search would perform N steps, N being the size of the list.

So how do we prove that a linear search is truly linear in nature?

We can increase the number of search iterations. When we search a list repeatedly, the effects of factors not in our control averages out — and we get a plot that is much more linear in nature.

Linear Search: Each plot was generated while searching a list repeatedly for 10, 100 and 1000 times

As we notice in the above graph, if the same sample is searched multiple times with the linear search — the effects of known unknowns become smaller gradually and we get a plot that is almost linear.

Lastly, let’s prove that a linear search algorithm is really linear in nature.

Linear Search: The list was searched 1000 times for each sample size

In the above plot time mean time taken for 10000 iterations is 0.18 milliseconds. When the size of list is doubled to 20000 iterations the average time doubles (almost) to 0.35 milliseconds . When the list size becomes 100000 (10 times the initial list size) the search time is also approximately10 times 1.76 milliseconds.

Since the average execution time for linear search is directly proportional to the size of the list the time complexity of linear search if O(n)

Binary Search

Binary Search is a searching algorithm used in a sorted list by repeatedly dividing the search interval in half.

Following is the graph of a list being searched using the binary search algorithm.

Each sample size was searched 10000 times to obtain the search time. Search times for linear search were noted in milliseconds linear search , while for binary search they are noted in microseconds (1 millisecond = 1000 microseconds)

Binary Search: The list was searched 10000 times for each sample size

Unlike linear search where the graph clearly illustrates the relationship between list size and search time over a large number of search iterations, in case of the binary the relationship between list size and search time is not evident from the plot.

Theoretically, it can be proven that for the binary search the time complexity is O(Log N) i.e the search time is proportional to the log of list size.

In the plot above the initial list size is 10000 elements and the average search time for is 3.358 micro seconds.

Since the time complexity of binary search is log(N), the search time for the next list in our experiment with 20000 elements should be

3.358 ✖️ ( log(20000) ➗log(10000) ) = 3.61 microseconds

Binary search time for a list of size 30000 should be

3.358 ✖️ ( log(30000) ➗log(10000) ) = 3.75 microseconds

Following is the expected versus actual search time for a binary list. The expected search time is calculated using the base list size of 10000 elements and search time of 3.358 micro seconds.

Binary Search: Expected search times based compared with actual Search times

Linear Search Versus Binary Search

Plot comparing times of binary and linear search algorithms. Binary Search times barely increase as the list size is increased.

Linear Search of an Ordered List

As we know a linear search algorithm does not need the list to be ordered.

But how is the performance of a linear search impacted if the list is ordered.

I was intrigued by this question. So I put the search executor to work, but this time instead of comparing linear search to binary search — I compared linear search for an unordered list to linear search of an ordered list.

I expected the plots to overlap. But what I found was that as the list size increases, the search over an ordered list seems to take longer than the search over the unordered list.

Please note: The time to order the data is not part of the search times. The data was ordered before it was passed to the search function.

The search times over list size for linear search: Ordered vs Unordered list

It would be interesting to investigate why this is happening. My guess is that , the searched value , that is generated by a random integer generator — falls in the upper range of the search data — and because of that for an ordered list the linear search has to always perform at least N/2 steps, N being the sample size.

Thank You

Hope you enjoyed this article. Please suggest any errors, or scope for improvements.

There are more to come, so please stay tuned.

If you would like the csv file with search times and sample sizes employed to generate these plots please comment below or send me a message. I would be happy to share.