C Programming

Linear Search Time Complexity

Linear Search is Sequential Search. This method of searching checks the elements of the list one-by-one, beginning from the first element. When it sees the first occurrence of the element it is looking for, the searching stops. The element it is looking for is called the target. If the element is not found, all the elements in the list are checked. Linear search is a very simple search algorithm that every programmer should learn, either officially or intuitively.

Consider the following list:

I J A C B G D H E F

To look for A, the program has to iterate the list 3 times. To look for G, the program has to iterate the list 6 times. To look for F, the program has to iterate the list 10 times. To look for K or any letter that is not in the list, the program has to iterate the list 10 times, and will not find a match.

The aim of this article is to produce the time complexity for linear search. Programming is done in the following C discussion.

Linear Search Algorithm

The algorithm for linear search is straight forward. Assume that the list is a zero-indexed based array. Let the variable that represents each index be i. Let the array have the name A. The steps are as follows:

    • Let i be 0.
    • If A[i] is the target, the value for i is returned and the search ends successfully.
    • If A[i] is not the target, increase i by 1 and repeat the previous step.
    • While i is less than n, where n is the length of the array, keep repeating the previous two steps in order.
    • Continue this way until the target is either found or not found.

The search ends successfully when the target is found. The search ends unsuccessfully when the target is not found. For an unsuccessful ending, all the n elements are checked.

Time Complexity

Time complexity is the number of main operations for some code to complete its task. Checking if the target matches an element is one operation. There is the worse-case time complexity, average-case time complexity, and best-case time complexity.

Worse-Case Time Complexity

The maximum number of operations occurs when the target is at the end of the list or is not in the list at all. This is the worse-case. The worse-case time complexity is given as:

O(n)

This uses the Big-O notation. The Big-O notation begins with the uppercase O, followed by parentheses. Inside the parentheses is the expression for the number of operations to solve the task.

Best-Case Time Complexity

If the first element of the list is the target, only one checking operation is necessary for the search. That is, only one operation is necessary for the search. This is the best-case time complexity. It is written as:

O(1)

Where 1 in the parentheses means one operation.

Average-case Time Complexity

Average-case time complexity depends on the probability distribution. If each element can be in any position, then each element is equally likely to be searched. In this situation, the average-case time complexity is given as:

O(n/2)

Programming in C

Linear search is probably the easiest search to write a program for. Just follow the algorithm, which is repeated here, for easy reference:

    • Let i be 0.
    • If A[i] is the target, the value for i is returned and the search ends successfully.
    • If A[i] is not the target, increase i by 1 and repeat the previous step.
    • While i is less than n, where n is the length of the array, keep repeating the previous two steps in order.
    • Continue this way until the target is either found or not found.

Essentially, the program is as follows:

    #include <stdio.h>

    int linearSearch(char A[], int N, char T) {
        for (int i=0; i<N; i++) {
            if (T == A[i])
                return i;
        }
    }

 
It begins by including the stdio.h library which is responsible for the input and output. After that, there is the linearSearch() function definition. The main code in the function definition is the for-loop. The for-loop scans the array from the beginning to the end, looking for a match of the target. If a target is found, the index for the matching element in the array is returned. In order to obtain the ordinal number of the index of the matched element, add 1 to the zero-based index.

A suitable C main function for the above program is as follows:

    int main(int argc, char **argv)
    {
        int n = 10;
        char A[] = {'I', 'J', 'A', 'C', 'B', 'G', 'D', 'H', 'E', 'F'};

        int ret = linearSearch(A, n, 'G');

        printf("%i\n", ret);

        return 0;
    }

 
The first statement of the C main function declares the number of elements in the given array. After that, there is the array with the name A. There are ten characters in the array. The declaration of the array begins with “char” and not “int”. From there, the defined linearSearch() function is called. The first argument to the function call is the array. The second argument is the number of elements in the array. The third argument is the target which is the letter whose presence in the array is checked. If it is present, the zero-based index is returned. If it is not present, nothing is returned.

The next statement prints any index returned. For this C main function, 5 is printed out. If 1 is added to 5, it would be 6, which is the ordinal index.

Conclusion

The worse-case time complexity is given as:

O(n)

This uses the Big-O notation. The Big-O notation begins with the uppercase O, followed by parentheses. Inside the parentheses is the expression for the number of operations to solve the task.

If the first element of the list is the target, only one checking operation is necessary for the search. That is, only one operation is necessary for the search. This is the best-case time complexity. It is written as:

O(1)

Where 1 in the parentheses means one operation.

The average-case time complexity depends on the probability distribution. If each element can be in any position, then each element is equally likely to be searched by this algorithm. In this situation, the average-case time complexity is:

O(n/2)

About the author

Chrysanthus Forcha

Discoverer of mathematics Integration from First Principles and related series. Master’s Degree in Technical Education, specializing in Electronics and Computer Software. BSc Electronics. I also have knowledge and experience at the Master’s level in Computing and Telecommunications. Out of 20,000 writers, I was the 37th best writer at devarticles.com. I have been working in these fields for more than 10 years.