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).
References:
- https://www.youtube.com/watch?v=zUUkiEllHG0&list=PLDV1Zeh2NRsB6SWUrDFW2RmDotAfPbeHu&index=3
- https://en.wikipedia.org/wiki/Logarithm
- https://en.wikipedia.org/wiki/Natural_logarithm
- Intro to Programming and Computation: Chapters 9.1–9.3.1, 9.3.3, and 9.3.5
- https://www.youtube.com/watch?v=7lQXYl_L28w&list=PLUl4u3cNGP63WbdFxL8giv4yhgdMGaZNA&index=38&t=0s
- https://eli.li/2022/01/26/notes-on-big-o-notation
Last modified: 202201312136