In this article, we have presented the Mathematical Analysis of Time and Space Complexity of Linear Search for different cases such as Worst Case, Average Case and Best Case. We have presented the exact number of comparisons in Linear Search and Time Complexity in Big-O notation.

Table of content:

1. Basics of Linear Search
2. Analysis of Best Case Time Complexity of Linear Search
3. Analysis of Average Case Time Complexity of Linear Search
4. Analysis of Worst Case Time Complexity of Linear Search
5. Analysis of Space Complexity of Linear Search
6. Conclusion

In short:

• Best Case Time Complexity of Linear Search: O(1)
• Average Case Time Complexity of Linear Search: O(N)
• Worst Case Time Complexity of Linear Search: O(N)
• Space Complexity of Linear Search: O(1)

Basic of Linear Search

To get a better understanding of Linear Search, go through these articles:

• Linear Search Algorithm in depth
• Questions/ MCQ on Linear Search Algorithm

In short, Linear Search Algorithm is an algorithm which checks all elements in a given list sequentially and compares with element with a given element which is the element being searched. This algorithm is used to check if an element is present in a list.

Following is the implementation of Linear Search in C:

#include <stdio.h>
/*
 * Part of Cosmos by OpenGenus Foundation
 * Input: an integer array with size in index 0, the element to be searched
 * Output: if found, returns the index of the element else -1
*/
int search(int arr[], int size, int x)
{
    int i=0;
    for (i=0; i<size; i++)
        if (arr[i] == x)
            return i;
    return -1;
}
int main()
{
    // Index 0 stores the size of the array (initially 0)
    int arr[] = {2,3,1,5};
    int size = sizeof(arr) / sizeof(arr[0]);
    int find = 1;
    printf("Position of %d is %d\n", find, search(arr,size,find));
    return 0;
}

We will start with the Mathematical Analysis of Linear Search.

Analysis of Best Case Time Complexity of Linear Search

The Best Case will take place if:

• The element to be search is on the first index.

The number of comparisons in this case is 1. Thereforce, Best Case Time Complexity of Linear Search is O(1).

Analysis of Average Case Time Complexity of Linear Search

Let there be N distinct numbers: a1, a2, ..., a(N-1), aN

We need to find element P.

There are two cases:

• Case 1: The element P can be in N distinct indexes from 0 to N-1.
• Case 2: There will be a case when the element P is not present in the list.

There are N case 1 and 1 case 2. So, there are N+1 distinct cases to consider in total.

If element P is in index K, then Linear Search will do K+1 comparisons.

Number of comparisons for all cases in case 1 = Comparisons if element is in index 0 + Comparisons if element is in index 1 + ... + Comparisons if element is in index N-1
= 1 + 2 + ... + N
= N * (N+1) / 2 comparisons

If element P is not in the list, then Linear Search will do N comparisons.

Number of comparisons for all cases in case 2 = N

Therefore, total number of comparisons for all N+1 cases = N * (N+1) / 2 + N
= N * ((N+1)/2 + 1)

Average number of comparisons = ( N * ((N+1)/2 + 1) ) / (N+1)
= N/2 + N/(N+1)

The dominant term in "Average number of comparisons" is N/2. So, the Average Case Time Complexity of Linear Search is O(N).

Analysis of Worst Case Time Complexity of Linear Search

The worst case will take place if:

• The element to be search is in the last index
• The element to be search is not present in the list

In both cases, the maximum number of comparisons take place in Linear Search which is equal to N comparisons.

Hence, the Worst Case Time Complexity of Linear Search is O(N).

Number of Comparisons in Worst Case: N

Analysis of Space Complexity of Linear Search

In Linear Search, we are creating a boolean variable to store if the element to be searched is present or not.

The variable is initialized to false and if the element is found, the variable is set to true. This variable can be used in other processes or returned by the function.

In Linear Search function, we can avoid using this boolean variable as well and return true or false directly.

The input to Linear Search involves:

• A list/ array of N elements
• A variable storing the element to be searched.

As the amount of extra data in Linear Search is fixed, the Space Complexity is O(1).

Therefore, Space Complexity of Linear Search is O(1).

Conclusion

As a conclusion:

• Best Case Time Complexity of Linear Search: O(1)

• Average Case Time Complexity of Linear Search: O(N)

• Worst Case Time Complexity of Linear Search: O(N)

• Space Complexity of Linear Search: O(1)

• Number of comparisons in Best Case: 1

• Number of comparisons in Average Case: N/2 + N/(N+1)

• Number of comparisons in Worst Case: N

With this, you have the complete idea of Linear Search and the analysis involving it. Enjoy.