What is Big O?
Big O notation is a mathematical notation that describes the limiting behavior of a function as the argument approaches a particular value or infinity. In computer science, it is used to classify algorithms based on how their runtime or space requirements increase as the input size increases.
Common complexities
- O(1) - Constant Time
- O(log n) - Logarithmic Time
- O(n) - Linear Time
- O(n log n) - Linearithmic Time
- O(n2) - Quadratic Time
- O(2n) - Exponential Time
Temporal Complexity vs. Spatial Complexity
Temporal Complexity
Measures the amount of time an algorithm takes to complete based on the input size. It helps us understand how the algorithm's performance scales with larger inputs.
Spatial Complexity
Measures the amount of memory space required by an algorithm based on the input size. This includes both auxiliary space and the space used by the input.