BigO Notation
BigO notation shows the speed of an algorithm at a large scale in the worstcase 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 BigO notation will be how long it takes to find that.
Common Notations
BigO 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. 
Loglinear  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 BigO notation
Since BigO 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 BigO will see the largest possible number or exponent (n^3
) and use that: O(n^3)
.
BigO 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/notesonbigonotation
Last modified: 202201312136