Binary Search Time Complexity Analysis

Binary Search Time complexity: O(log n)


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

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)

Leave a Reply

Your email address will not be published. Required fields are marked *