Big-O notation is used to mathematically describe the runtime and memory usage required for an algorithm to process data.
Since big-O is a mathematical expression, it’s helpful to brush up on your math skills when studying big-O. I recommend Kahn Academy for this.
O(1) - Will always run in the same amount of time regardless of the amount of data it’s processing.
O(N) - The runtime will grow linearly with the size of the data.
O(N^2) - Exponential growth.
As you can see N is the data, or the number of items the algorithm processes. An algorithm with a runtime of O(N^2) is processing each element exponentially. This is often the case for nested for loops like the example below:
for level1 in numbers:
result = 0
for level2 in numbers:
result += level1 * level2
print(result)
General principles for calculating Big-O are:
- Different steps get added
- Drop constants
- Different inputs are assigned to different variables
- Drop non-dominant terms
Logarithms
A logarithm is the inverse of an exponent. Binary searches have logarithmic run times because adding more elements has little effect on the runtime of the algorithm. A binary search is represented as O(log N).
References and Learning
- https://rob-bell.net/2009/06/a-beginners-guide-to-big-o-notation
- Cracking the Coding Interview by Gayle Laakmann McDowell