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