Question

The complexity of linear search algorithm is: 
1. O (n) 
2. O (n*n) 
3. O (log n) 
4. O (n log n) 

Answer 1

Correct Answer - Option 1 : O (n) 

Concept:

Linear search : Search is an operation in which a given list is searched for a particular value. A list can be searched sequentially wherein the search for the data item starts from the beginning and continues till the end of the list. This search method is known as linear search.

Explanation:

Algorithm:

1) Take first element and compare this with the element we want to search.

2) If matches, then go to step 5.

3) Else, consider next element and go to step 1. 

4) If element not found, then go to step 6.

5) element found, then return the location of element.

6) Exit

Linear search makes n/2 comparisons on an average where n is the number of elements. At the most, linear search takes n comparisons. 

So, overall complexity in the worst case of linear search algorithm is O(n).