PHP 7 Data Structures and Algorithms

Analysis of binary search algorithm

So far, we have seen that for each iteration, we are dividing the list by half and discarding one half completely for searching. This makes our list look like n/2, n/4, n/8, and so on after 1, 2, and 3 iterations, respectively. So, we can say that after Kth iteration, n/2^k items will be left. We can easily say that, the last iteration occurs when n/2^k = 1, or we can say that, 2^K = n. So, taking log from both side yields, k = log(n), which is the worst case running time for binary search algorithm. Here is the complexity for binary search algorithm:

Best time complexity	O(1)
Worst time complexity	O(log n)
Average time complexity	O(log n)
Space complexity (worst case)	O(1)

If our ...