Binary Search Time complexity: O(log n)
Analysis
Since at each step the size of the (searchable) array is reduced to half (1/2), we could write the following recurrence relation for the Binary Search Algorithm:
T(n) = T(n/2) + 1
Using substitution, we get:
T(n) = T(n/4) + 1 + 1 or,
T(n) = T(n/2^2) + 2
Similarly,
T(n) = T(n/2^k) + k
This will continue until n = 2^k i.e. until k = logn . Thus,
T(n) = T(1) + logn, which is:
T(n) = O(log n)