Definition
Big-O notation describes the upper bound of the growth rate of an algorithm. Written as O(f(n)), it represents the worst-case scenario for the algorithm's resource usage.
Common Complexities
From Best to Worst
- O(1) - Constant
- O(log n) - Logarithmic
- O(n) - Linear
- O(n log n) - Linearithmic
- O(n²) - Quadratic
- O(2ⁿ) - Exponential
- O(n!) - Factorial
Common Examples
- O(1): Array access
- O(log n): Binary search
- O(n): Linear search
- O(n log n): Merge sort
- O(n²): Bubble sort
- O(2ⁿ): Recursive Fibonacci
- O(n!): Traveling salesman