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

Transform Your Career

Choose from our industry-leading programs designed for career success

NSDC Certified

Modern Software and AI Engineering Program

Master full-stack development with AI integration

12 MonthsDuration

AI-LedCurriculum

Career SupportSupport

+1000 more

Go to Program

NSDC Certified

Modern Data Science and ML with specialisation in AI

Advanced data science techniques with AI specialization

12 MonthsDuration

AI-LedCurriculum

Career SupportSupport

+1000 more

Go to Program

NSDC Certified

Advanced AIML with Specialisation in Agentic AI

Deep dive into AIML with focus on Agentic systems

12 MonthsDuration

AI-LedCurriculum

Career SupportSupport

+1000 more

Go to Program

NSDC Certified

DevOps, Cloud & AI Platform Engineering

Build and manage AI-powered cloud infrastructure

12 MonthsDuration

AI-LedCurriculum

Career SupportSupport

+1000 more

Go to Program

NSDC Certified

AI Engineering Advanced Certification by IIT-Roorkee

Premier AI engineering certification from IIT-Roorkee

3 MonthsDuration

AI-LedCurriculum

Career SupportSupport

Go to Program

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).