‘O(log n)‘ refers to a logarithmic time complexity in the big O notation. This implies that the running time of an algorithm increases logarithmically in proportion to the size of the input data set.
Logarithmic time refers to an algorithm that improves performance as the data set increases. These algorithms apply to scenarios where an algorithm repeatedly reduces the size of the input data to achieve a result, such as in a binary search.
The most standard example of an algorithm with an ‘O(log n)‘ time complexity is indeed the binary search algorithm.
# Binary Search Algorithm
The binary search algorithm is a search algorithm that finds the location of a target value within a sorted array. It compares the target value to the middle element of the array and, based on that comparison, can disregard half of the array. Given sorted elements, the algorithm continues to divide the search space in half until the target value is found.
Here’s a simple implementation of Binary Search in Python:
def binary_search(arr, low, high, x):
if high >= low:
mid = (high + low) // 2
if arr[mid] == x:
return mid
elif arr[mid] > x:
return binary_search(arr, low, mid - 1, x)
else:
return binary_search(arr, mid + 1, high, x)
else:
return -1# Proof of Time Complexity of Binary Search:
Our task is to find one element in an array of size ‘n‘. Let’s denote ‘T(n)‘ as the number of comparisons in the worst case for an array of size ‘n‘.
As we are dividing array in half at each step, the relation we get is:
T(n) = T(n/2) + 1
This is a recurrence relation. Solving it yields ‘T(n) = O(log n)‘.
The ‘+1‘ in the recurrence relationship stems from the fact that each operation (i.e., checking the midpoint of the array/sub-array) takes constant ‘O(1)‘ time.
In other words, if we have ‘n‘ elements, in the worst case we need:
- 1 iteration to halve ‘n‘ elements to ‘n/2‘
- 1 iteration to halve ‘n/2‘ elements to ‘n/4‘
- and so on...
Continuing this process, we see that the maximum number of iterations to find a value, or realize it is not in the array, is the number of times you can halve the ‘n‘, plus one, which mathematically equals ‘log_2 n + 1‘.
This proves that Binary Search is an ‘O(log n)‘ operation in the worst case scenario.
It’s important to stress again that, because the run-time complexity of Binary Search is ‘log n‘, it’s one of the most efficient algorithms we have in computer science. The difference becomes especially apparent for large numbers.