O(yeah)
Big O Notation — JavaScript
We use Big O Notation to analyze the performance of an algorithm.
Big O Notation:
- gives us a high-level understanding of an algorithm’s complexity
- gives us a generalized way to talk about how efficient an algorithm is
- only cares about general trends (e.g. linear? quadratic? constant?)
- gives us the worst-case scenario/upper bound
- depends only on the algorithm, not the hardware used to run it
Time Complexity
How can we analyze the run time of an algorithm as the input size grows?
Big O allows us to talk formally about how the run time of an algorithm grows as the input grows. It shows us the relationship between the input size and the time relative to the input.
Constant Time Complexity
O(1) — always the same number of operations; completes in the same amount of CPU time regardless of the input size
- Arithmetic operators
- Variable assignment
- Accessing elements in an array or an object
Linear Time Complexity
O(n) — as n grows the run time roughly grows proportionately
- loops
Quadratic Time Complexity
O(n²) — as n increases, the run time increases roughly at the rate of n²
- nested loops
In a loop, the complexity is the length of the loop times the complexity of whatever happens inside the loop
Space Complexity
How much additional memory do we need to allocate to run the code in our algorithm?
Big O allows us to talk formally about how the space required by an algorithm grows as the input grows. It shows us the relationship between the input size and the memory that’s taken up relative to the input.
Constant Space Complexity
O(1) — always the same amount of memory regardless of the input size
- Most primitives (booleans, numbers, undefined, null)
Linear Space Complexity
O(n) — as n grows the space needed roughly grows proportionately
- Strings, where n is the string length
- Arrays, where n is the length
- Objects, where n is the number of keys
Simplifying Big O Expressions
- Constants Don’t Matter
- O(500) → O(1)
- O(2n) → O(n)
- O(13n²) → O(n²)
2. Smaller Terms Don’t Matter
- O(n + 10) → O(n)
- O(1000n + 50) → O(n)
- O(n² + 5n + 8) → O(n²)
- O(n + 6 + n³ + 4n²) → O(n³)
Logarithms
Complexity grows logarithmically in relation to n: the inverse of exponentiation.
The logarithm of a number measures the number of times you can divide that number by 2 before you get a value that’s less than or equal to 1.
1. 8 / 2 = 4
2. 4/2 = 2
3. 2/2 = 1
log(8) = 3 → 2³ = 8
log(value) = exponent → 2^exponent = value
Logarithmic Complexity
O(log n) — complexity grows logarithmically in relation to the input.
- Searching algorithms (e.g. binary search)
- Efficient sorting algorithms (e.g. heap sort, merge sort)
- Recursion (sometimes involves logarithmic space complexity)
