Linear Search Time Complexity Analysis: Part 1


Linear search is one of the simplest algorithms. Consider an unsorted array A of size n. Given an element x, we would like to determine whether x exits in A or not. Linear search goes like this: search A for x in order by considering A[1], A[2], …, A[n] until either it finds A[i] = x or it reaches the end of the array which means that the element does not exist. Because the algorithm always starts at 1 and continue sequentially up to n, we call it deterministic. We don’t make any assumptions about whether A contains one or more equal copies of the same element. However, we assume that the elements of the array, whatever they are, are equally likely to appear in any order. Also we will consider only the number of comparisons that involves elements from A when computing the running time.

Assuming that there is only one index i such that A[i] = x, what is the worst-case running time of linear search?
Obviously n since in the worst case, A[n] = x and so we have to make n comparisons.

Assuming that there are k >= 1 indices such that A[i] = x, what is the worst-case running time of linear search?
In the worst case, all of them would occupy indices n-k+1 up to n so we have to make n-k+1 comparisons.

Assuming that there are no indices such that A[i] = x, what is the worst-case running time of linear search?
Since we have to compare all elements of A, we make n comparisons.

That was very easy, however, it serves as an introduction to the more complex analysis. In the next part of the series, I will discuss the average-case running time of linear search in the three cases mentioned above. For the sake of completeness and as an exercise for the reader, determine the exact best-case running time of linear search in the three cases.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s