Open-Source Internship opportunity by OpenGenus for programmers. Apply now.

In this article, we have presented the Mathematical Analysis of Time and Space Complexity of Binary Search for different cases such as Worst Case, Average Case and Best Case. We have presented the exact number of comparisons in Binary Search.

Note: We have denoted the Time and Space Complexity in Big-O notation.

Table of content:

Basics of Binary Search
Analysis of Best Case Time Complexity of Binary Search
Analysis of Average Case Time Complexity of Binary Search
Analysis of Worst Case Time Complexity of Binary Search
Analysis of Space Complexity of Binary Search
Conclusion

In short:

Best Case Time Complexity of Binary Search: O(1)
Average Case Time Complexity of Binary Search: O(logN)
Worst Case Time Complexity of Binary Search: O(logN)
Space Complexity of Binary Search: O(1) for iterative, O(logN) for recursive.

Basics of Binary Search

Go through these articles to understand Binary Search completely:

Binary Search is an algorithm is efficiently search an element in a given list of sorted elements. Binary Search reduces the size of data set to searched by half at each step.

The iterative implementation of Bianry Search is as follows:

int binarySearch(int[] A, int x)
{
    int low = 0, high = A.length - 1;
    while (low <= high)
    {
        int mid = (low + high) / 2;
        if (x == A[mid]) {
            return mid;
        }
        else if (x < A[mid]) {
            high = mid - 1;
        }
        else {
            low = mid + 1;
        }
    }
    return -1;
}

Let us get started with the mathematical analysis of Binary Search.

Best Case Time Complexity of Binary Search

The best case of Binary Search occurs when:

The element to be search is in the middle of the list

In this case, the element is found in the first step itself and this involves 1 comparison.

Therefore, Best Case Time Complexity of Binary Search is O(1).

Average Case Time Complexity of Binary Search

Let there be N distinct numbers: a1, a2, ..., a(N-1), aN

We need to find element P.

There are two cases:

Case 1: The element P can be in N distinct indexes from 0 to N-1.
Case 2: There will be a case when the element P is not present in the list.
There are N case 1 and 1 case 2. So, there are N+1 distinct cases to consider in total.

If element P is in index K, then Binary Search will do K+1 comparisons.

This is because:

The element at index N/2 can be found in 1 comparison as Binary Search starts from middle.

Similarly, in the 2nd comparisons, elements at index N/4 and 3N/4 are compared based on the result of 1st comparison.

On this line, in the 3rd comparison, elements at index N/8, 3N/8, 5N/8, 7N/8 are compared based on the result of 2nd comparison.

Based on this, we know that:

Elements requiring 1 comparison: 1
Elements requiring 2 comparisons: 2
Elements requiring 3 comparisons: 4

Therefore, Elements requiring I comparisons: 2^(I-1)

The maximum number of comparisons = Number of times N is divided by 2 so that result is 1 = Comparisons to reach 1st element = logN comparisons

I can vary from 0 to logN

Total number of comparisons = 1 * (Elements requiring 1 comparison) + 2 * (Elements requiring 2 comparisons) + ... + logN * (Elements requiring logN comparisons)

Total number of comparisons = 1 * (1) + 2 * (2) + 3 * (4) + ... + logN * (2^(logN-1))

Total number of comparisons = 1 + 4 + 12 + 32 + ... = 2^logN * (logN - 1) + 1

Total number of comparisons = N * (logN - 1) + 1

Total number of cases = N+1

Therefore, average number of comparisons = ( N * (logN - 1) + 1 ) / (N+1)

Average number of comparisons = N * logN / (N+1) - N/(N+1) + 1/(N+1)

The dominant term is N * logN / (N+1) which is approximately logN. Therefore, Average Case Time Complexity of Binary Search is O(logN).

Analysis of Worst Case Time Complexity of Binary Search

The worst case of Binary Search occurs when:

The element is to search is in the first index or last index

In this case, the total number of comparisons required is logN comparisons.

Therefore, Worst Case Time Complexity of Binary Search is O(logN).

Analysis of Space Complexity of Binary Search

In an iterative implementation of Binary Search, the space complexity will be O(1).

This is because we need two variable to keep track of the range of elements that are to be checked. No other data is needed.

In a recursive implementation of Binary Search, the space complexity will be O(logN).

This is because in the worst case, there will be logN recursive calls and all these recursive calls will be stacked in memory. In fact, if I comparisons are needed, then I recursive calls will be stacked in memory and from our analysis of average case time complexity, we know that the average memory will be O(logN) as well.

Conclusion

The conclusion of our Time and Space Complexity analysis of Binary Search is as follows:

Best Case Time Complexity of Binary Search: O(1)
Average Case Time Complexity of Binary Search: O(logN)
Worst Case Time Complexity of Binary Search: O(logN)
Space Complexity of Binary Search: O(1) for iterative, O(logN) for recursive.

With this article at OpenGenus, you must have the complete idea of analyzing Binary Search algorithm. Enjoy.

Time & Space Complexity of Binary Search [Mathematical Analysis]

Time Complexity Algorithms Search Algorithms