Binary Search Algorithm Time Complexity

Question

What I have studied in Cormen book that Time complexity of Binary Saerch Algorithm is:

• Best Case - O (1)

• Worst Case - O (log n)

My doubt is how come they have written both the complexities directly in Big O notation. Can I say that Best Case Complexity is Theta (1) and Worst Case Complexity is Theta (log n) ?

Answer 1

Yes, you can say that the best-case running time complexity for the binary search algorithm is Theta(1) and that the worst-case running time complexity for the binary search algorithm is Theta(log n). To explain this, we delve into the definitions of Big O, Big Omega, and Big Theta which are all asymptotic notations to describe the running time and space complexities of algorithms.

When referring to the best/worst-case running time of an algorithm, you are typically referring to a single function. Big O notation is used to describe algorithms by their upper bound running time and Big Omega notation is used to describe algorithms by their lower bound running time.

Stated in a simpler way, Big O means that the algorithm cannot and will not run any slower than the function bounded within Big O. Big Omega means that the algorithm cannot and will not run any faster than the function bounded within Big Omega. In order to use Big Theta notation to describe the running time complexity of an algorithm, the running time of the algorithm must include the same function for both Big O and Big Omega notations.

In the case of Binary Search, the best case is described to be the case when the first element in the search algorithm is the element or item that you are searching for. This means that no matter what happens, the algorithm will only have to look at no more and no less than one singular item. Therefore, this situation can be described to have a running time of O(1) and Omega(1). Since these two functions are the same, it is correct to say that the binary search algorithm’s best-case running time is Theta(1).

The worst case of Binary Search is described to be the case when every element needs to be looked at and the last element checked is the element that the search is looking for, or the element simply does not exist within the data structure. Since Binary Search utilizes the concept of Divide and Conquer to look at every element, it is trivial that the running time of the algorithm in its worst-case must be bounded by some form of (log n). Specifically, we can say that it would have a running time of both O(log n) and Theta(log n) because the algorithm would not be able to run any faster or any slower due to the set number of elements that it must look at. In this case, the two functions are the same, so it is correct to say that the binary search algorithm’s worst-case running time is Theta (1).