# 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,10,15,17,2,16,20 };
int result = findElement(arr, 2);

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

}
else {