How do we compare algorithm efficiency without being tied to specific hardware or machine details?
Big O notation describes the upper bound on the growth rate of a function, allowing comparison of algorithms based on how their resource requirements scale with input size, ignoring machine-dependent constants.
Big O describes asymptotic behavior as input grows large:
- O(1) - constant time
- O(log n) - logarithmic time
- O(n) - linear time
- O(n²) - quadratic time
- O(2^n) - exponential time
The notation focuses on dominant terms, ignoring lower-order terms and constants.
- Describes upper bound (worst-case growth)
- Ignores machine-specific constants
- Focuses on asymptotic behavior
- Used for time and space complexity
- Essential for comparing algorithms
- Built from: Asymptotic Analysis
- Builds into: Computational Complexity Theory, Time Complexity, Space Complexity
- Related: Algorithm, Big Ω Notation, Big Θ Notation
- Big O gives upper bound—actual performance may be better
- Constants matter in practice for small inputs
- Must consider best, average, and worst case