Time complexity of linear search

The time complexity of linear search is O(n).  In the best case its time complexity is O (1).

In the linear search, you search an element in a list sequentially until you find that element.

For example,

Suppose you want to find the element 2 in the given list below. You have to traverse the list and compare each element one by one till you find 2 in the list.

LIST: |7 | 10 |15|17| 2| 16 |20 |

If you find the element you are searching for is at very first in the list, for example 7, then the time complexity would be O (1).

Or else it’ll take O(n) time. Even in the worst case you’ll find the element at the last of the list, or you don’t find at all.

The n is the number of elements in the list.

Little more elaboration:

Let’s say you want to find 10.

First you compare with 7, and then with 10. So, there are 2 comparisons.

Let’s say you want to find 17.

First you compare with 7, and then with 10, and then 15, then 17.  So, there are 4 comparisons.

Similarly, if you have n elements in the list, you may require n comparisons.  So, the time complexity of linear search would be O(n).

Interesting read: Big-O notations with graphical representation.

Code Example of Linear Search:

This program will search the target element you want to find by comparing each elements sequentially one by one. – Linear search example.

The code is in C but you can easily understand with any programming language.

#include<stdio.h>

#define SIZE 7
int findElement(int arr[] , int search) {
	int found = 0;
	for (int i = 0; i < SIZE; ++i) {
		if (arr[i] == search) {
			found = 1;
			break;
		}
	}
	return found;
}

int main() {

	int arr[7] = { 7,10,15,17,2,16,20 };
	int result = findElement(arr, 2);

	if (result) {
		printf("Element found");

	}
	else {
		printf("Element not found");
	}
	
	return 0;
}