Time and Space Complexity of Binary Search

Binary Search is an efficient algorithm designed for searching within a sorted list of items. Its approach involves iteratively dividing the search space in half, until the target element found in the array.

The time complexity of the Binary Search Algorithm is $O(log_2{n})$, Where n is the size of the sorted linear array. It means the complexity grows logarithmically as the size of array increases and the space complexity of its algorithm is $O(1)$.

Time Complexity of Binary Search

Best Case Time Complexity of Binary Search

The best case scenario of Binary Search occurs when the target element is in the central index.In this situation, there is only one comparison.
Therefore, the Best Case Time Complexity of Binary Search is O(1).

Average Case Time Complexity of Binary Search

The average case arises when the target element is present in some location other than the central index or extremities. The time complexity depends on the number of comparisons to reach the desired element.

In the following iterations, the size of the subarray is reduced using the result of the previous comparison.
– Initial length of array $= n$
– Iteration 1 – Length of array $= n/2$
– Iteration 2 – Length of array $= (n/2)/2 = n/2^2$
– Iteration k – Length of array $= n/2^k$

After k iterations, the size of the array becomes 1 (narrowed down to the first element or last element only).

Length of array $= n/2^k = 1$

=> $n = 2^k$

Applying log function on both sides:

=> $log_2{(n)} = log_2{(2^k)}$

=> $log_2{(n)} = k * log_2{2} = k$

=> $k = log_2(n)$

Therefore, the overall Average Case Time Complexity of Binary Search is O(logn).

Worst Case Time Complexity of Binary Search

The worst-case scenario of Binary Search occurs when the target element is the smallest element or the largest element of the sorted array.

Since the target element is present in the extremitites (first or last index), there are logn comparisons in total. Therefore, the Worst Case Time Complexity of Binary Search is O(logn).

Space Complexity of Binary Search

• In the case of the iterative approach, no extra space is used. Hence, the space complexity is O(1).
• In the worst case, logn recursive calls are stacked in the memory.
  • i comparisons require i recursive calls to be stacked in memory.
  • Since average time complexity analysis has logn comparisons, the average memory will be O(logn).

Thus, in recursive implementation the overall space complexity will be O(logn).

Conclusion

• Binary Search is used for finding the location of an element in a linear array.
• Binary search uses the divide and conquer technique.
• Learn What is the time complexity of binary search as follows:
  • Best Case – $O(1)$
  • Worst Case – $O(logn)$
  • Average Case – $O(logn)$
• The space complexity for binary search is
  • recursive approach – $O(logn)$
  • iterative approach – $O(1)$
• The equation T(n)= T(n/2)+1 is known as the recurrence relation for binary search.