# Big-O Notation

Big-O notation shows the speed of an algorithm at a large scale in the worst-case scenario using fuzzy estimates. If you are looking for an item in a list and the item is the last element in the list, then the Big-O notation will be how long it takes to find that.

## Common Notations

Big-O notation is usually represented as O(n), with mathematical formulas affecting the n inside. O represents the algorithm, n represents the number of elements.

Time Notation Description
Constant `O(1)` This always takes the same length of time, regardless of size. The code does not depend on the size of the problem.
Logarithmic `O(log(n))` log(n) being the inverse of exponentiation. Reduces the problem in half each time through process
Linear `O(n)` This takes the same amount of time as there are elements in the list. Simple iterative or recursive programs.
Log-linear `O(n\*log(n))`
Quadric `O(n^2)` Time goes up exponentially with the amount of elements.
Cubic `O(n^3)` Time goes up even more exponentially.
Exponential `O(b^n)` Time goes up an exponent per element. Nested loops or recursive calls.
Factorial `O(n!)` Time goes up by factorial.

## Rules of Thumb

### Constants can always be removed from a Big-O notation

Since Big-O only cares about the really biggest cases, as the numbers of elements in a list go up, even if there is a constant that is being added or multiplied, it won't affect the speed enough to matter. Exception being if the constant is of a very very large size, but even then, if the number of elements grows large enough.

### Use the largest exponent

If there is a formula that determines the length of time an algorithm will take, like `log(n)^3 + 15n^2 + 2n^3`, then Big-O will see the largest possible number or exponent (`n^3`) and use that: `O(n^3)`.

Big-O is 'rounding' to the nearest and simplest notation that is closest to the real outcome.

### Discerning the time taken per loop

In a program, if you have a loop over your list that will operate n times, you would write this as `f(n) = n = O(n)` If within that loop, you find another loop that will operate n*2 times: `f(n) = n * 2n = 2n^2 = O(n^2)`.