Big O Part 4 – Logarithmic Complexity

The raw performance of an algorithm, program, or a programmatic operation depends on a number of factors such, not least the computer it’s running on. Big O is not concerned with this; Big O describes the way the time taken by a program (or memory or space usage) depends on the amount of the data it has been given to work on in the first place. Big O tells us how well a program scales. We say that Big O describes the ‘complexity’ of a program.
This is the fourth in a series of videos about Big O. These videos show how various Big O time complexities can be derived for some well known algorithms including the linear search, stack push and pop operations, the bubble sort, the binary search and the merge sort. This particular video focuses on the binary search and logarithmic time complexity. It reviews the concept of logarithms and shows how these can apply to algorithms, such as the binary search, that take a divide and conquer approach.