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 zeroindexed 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 worsecase time complexity, averagecase time complexity, and bestcase time complexity.
WorseCase 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 worsecase. The worsecase time complexity is given as:
O(n)
This uses the BigO notation. The BigO notation begins with the uppercase O, followed by parentheses. Inside the parentheses is the expression for the number of operations to solve the task.
BestCase 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 bestcase time complexity. It is written as:
O(1)
Where 1 in the parentheses means one operation.
Averagecase Time Complexity
Averagecase 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 averagecase 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:
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 forloop. The forloop 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 zerobased index.
A suitable C main function for the above program is as follows:
{
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 zerobased 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 worsecase time complexity is given as:
O(n)
This uses the BigO notation. The BigO 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 bestcase time complexity. It is written as:
O(1)
Where 1 in the parentheses means one operation.
The averagecase 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 averagecase time complexity is:
O(n/2)