How to calculate binary search complexity
Binary search is also known as half-interval search or logarithmic search. It is a searching algorithm used to find the position of an element in the sorted array. Binary search runs in logarithmic time in the worst case you need to make O(log n) comparisons and binary search takes constant O(1) space.
Binary Search Complexity
The below sneppet shows you how to calculate it in the mathematical way and it’s very easy to understand if you know logarithm basics that you studied in your engineering. Please go through the Number Guess Game explained in the article Binary Search Number Guess Game.
Here the point is how many times (x) you divide the number of elements (n) by 2 until you find the correct number.
1 = n/2x
2x = n
Apply log2 on both sides
log2 2x = log2 n
x * log22 = log2 n
x * 1 = log2 n
Conclusion
x = log2 n means you can divide log n times until you find your element in the given array.