Time Complexity of Linear Search and Binary Search

This class will try to understand the Time Complexity of Linear Search and Binary Search.

The Linear Search and Binary Search algorithm has been explained in the data structures course.

Time Complexity of Linear Search and Binary Search

The linear and binary search algorithms are search algorithms used to search for the existence of the given element in the array.

Linear Search Time Complexity

The time complexity of the linear search is straightforward.

The algorithm for linear search is shown below.

In the above algorithm, the for loop will iterate for n times.

The number of iterations done by the loop is decided by the element’s position in the array.

For better understanding, we will consider the following array.

If the element to be searched is 2, it exists at the start of the array, and then the for loop will iterate only once. This case is the best case for the algorithm.

The algorithm’s efficiency is the Order of 1 O(1) in this case.

Similarly, if we are searching for 4, the for loop will do all the iterations because it exists at the end of the array.

This case is the worst-case possibility for the algorithm.

So, the efficiency of the linear search algorithm is O(n).

Binary Search Algorithm Time Complexity

The image below is the algorithm for binary search.

For a better understanding of binary search, we will consider the array as shown below.

The primary of the binary search algorithm is that the elements of the array should be in sorted order.

If the elements are in the sorted order, then the efficiency of the binary search algorithm is O(log n).

Here is the explanation for the above statement.

The design of the binary search algorithm is based on the divide and conquer technique.

We divide the given array based on the mid index of the array.

If the element to be searched is smaller than the mid element, the element will be on the left-hand side of the array only. If the element to be searched is greater than the mid element, then the element will be on the right-hand side of the array.

For example, on the above array, if we are searching for 3, then the element in the mid-position index is 4, and the element at index 4 is 5.

The following formula identifies the mid-element.

mid = FLOOR(( Low + High ) / 2).

As 3 is less than 5, we will only consider the left part of the array.

Again we will divide the array now the mid-element index is 2, and the element index is 3.

As the element to be searched is smaller than the mid-element, only the left part of the array is considered.

Now, the mid-element index of the remaining array is 1, and the element at index 1 is 2. This element is the element that we are searching for.

The index will be returned if the searched element is identified.

So, the logic behind this is if we have 8 elements, the maximum number of comparisons to be done is 3.

It means that log 8 comparisons are to be done.

So, the efficiency of the binary search algorithm is O(log n).