Linear Search Algorithm Analysis

Linear search is a commonly used searching method used by programmers. This article discusses the algorithm, its efficiency, best and worst case scenarios, loop invariant, and comparison with Binary Search. Subject: Computer Science, Course Code: CS101, University: Not mentioned

Running head: LINEAR SEARCH ALGORITHM ANALYSIS
Linear Search Algorithm Analysis
Name of the Student:
Name of the University:
Author note:

1
LINEAR SEARCH ALGORITHM ANALYSIS
The Linear Search Algorithm
Linear search is a very commonly used searching method used by most programmers
in order to search through a small list of elements. This kind of searching technique is also
known as the Sequential Searching algorithm. It is an extremely simple searching algorithm,
where a sequential search is conducted over all items in a list or array, one at a time. Every
element is checked for equality with the being searched element and if a match is found then
that particular element is displayed or returned. However, until the search element is spotted,
the searching goes on till the pointer reaches the end of the list (Deitel and Deitel 2008).
Algorithm
LinearSearch (array myArray, value searchElement)
Step 1: Set index i to 0
Step 2: if i >= length(myArray) then go to step-7, else go to next step
Step 3: if myArray [i] = searchElement, then go to step-6, else go to next step
Step 4: Increment i by 1
Step 5: Go to Step-2
Step 6: Print searchElement ‘Found at index i and go to step-8’
Step 7: Print ‘element not found’
Step 8: Exit
Java Code for the Linear Search Algorithm
public class Search{
public static int LinearSearch(int[] myArray, int searchElement){
int flag=0;
for(int i=0;i<myArray.length;i++){
if(myArray[i[==searchElement){

2
LINEAR SEARCH ALGORITHM ANALYSIS
System.out.println(searchElement+" found at index "+i);
return i;
}
}
System.out.println(searchElement+" not found.”);
return -1;
}
}
Efficiency
It is mathematically proven that the efficiency of a Linear Search algorithm is O(n),
‘n’ being the length of the array. This means that the loop counter has to traverse through the
entire loop in order to search for a particular element that is probably present at the last index
or may be is absent completely (Lafore 2017).
To analyse any algorithm, it is always necessary to consider the best case, the average
case and the worst case scenario for that particular algorithm.
Considering the example below, the iteration comparisons can be easily made for the
respective case scenarios.
Best Case Scenario
Suppose, for an array of length 10 with the following elements:
[ 15 , 12 , 16 , 20 , 45 , 33 , 19 , 25 , 30 , 10 ] and the element being searched for is 15.
Therefore, the element can be found with the linear search making the fewest
comparisons at index 0 itself. Therefore, for best case scenario, the loop exits with only one
iteration with a complexity of O(1).
Worst Case Scenario
Suppose, for an array of length 10 with the following elements:

3
LINEAR SEARCH ALGORITHM ANALYSIS
[ 15 , 12 , 16 , 20 , 45 , 33 , 19 , 25 , 30 , 10 ] and the element being searched for is 10.
The element being present at the very end of the loop, in this case, the counter will
have to iterate through the entire loop in order to spot the element being searched for. This
gives the algorithm a complexity of O(10) as the loop has to go through 10 iterations. This
would be the same if the item being searched for was absent from the array.
Therefore, it can be concluded that the Average Case iterations for the algorithm is
N/2.
Loop Invariant
All values present in the array at a lower index than the present loop iterator index
within the array, is not the value being searched (present searching index <= value index).
Therefore, if an element is present multiple times, then the loop counter is surely expected to
hit the first occurrence as index <= index of searched number.
Comparison with Binary Search
 The array list must be sorted in Binary Search but needs not to be so not in case of
Linear Search.
 The linear search method sequentially searches a set of data, whereas Binary search
uses a logical technique.
 The time complexity of linear search is O(n), whereas that for Binary search is O(log
n).
 The Linear search algorithm performs equality comparisons but the Binary search
algorithm performs ordering comparisons.

4
LINEAR SEARCH ALGORITHM ANALYSIS
References
Deitel, P.J. and Deitel, H.M., 2008. C++ how to Program. PearsonPrentice Hall.
Fletcher, R. and Reeves, C.M., 1964. Function minimization by conjugate gradients. The
computer journal, 7(2), pp.149-154.
Glass, H. and Cooper, L., 1965. Sequential search: A method for solving constrained
optimization problems. Journal of the ACM (JACM), 12(1), pp.71-82.
Lafore, R., 2017. Data structures and algorithms in Java. Sams Publishing.
Ravishankar, M., 1997, February. Some results on search complexity vs accuracy. In DARPA
Speech Recognition Workshop (pp. 104-107). Morgan Kaufmann Pub.
Weiss, M.A. and Hartman, S., 1998. Data structures and problem solving using Java (Vol.
204). Boston, MA: Addison-Wesley.