Big O Notation
Big O notation is a mathematical notation used to describe the upper bound of an algorithm's growth rate in terms of time or space, characterising its worst-case performance as the input size approaches infinity. It abstracts away constant factors and lower-order terms, focusing on the dominant factor that determines scalability. Big O is the industry standard language for comparing algorithm efficiency and is essential for technical interviews and software engineering.
Key Formula
f(n) = O(g(n)) if there exist constants c > 0 and n₀ > 0 such that f(n) ≤ c·g(n) for all n ≥ n₀
LaTeX: f(n) = O(g(n)) \iff \exists\, c > 0,\, n_0 > 0 : f(n) \le c \cdot g(n)\; \forall\, n \ge n_0
| Symbol | Meaning | Unit |
|---|---|---|
| f(n) | Actual running time or space of the algorithm | operations |
| g(n) | Bounding function (e.g., n², n log n) | dimensionless |
| c | Positive constant multiplier | dimensionless |
| n₀ | Threshold input size beyond which the bound holds | elements |
Worked Example
Problem
Prove that f(n) = 3n² + 5n + 2 is O(n²).
Solution
Step 1: We need to find c and n₀ such that 3n² + 5n + 2 ≤ c·n² for all n ≥ n₀. Step 2: For n ≥ 1, we have 5n ≤ 5n² and 2 ≤ 2n². Step 3: So 3n² + 5n + 2 ≤ 3n² + 5n² + 2n² = 10n². Step 4: Choose c = 10 and n₀ = 1.
Answer
f(n) = O(n²) with c = 10 and n₀ = 1.
Big O Notation Hierarchy (Slowest to Fastest Growth)
| Notation | Growth Rate | Common Name | Typical Use Case |
|---|---|---|---|
| O(1) | Constant | Constant | Hash table lookup |
| O(log n) | Logarithmic | Logarithmic | Binary search |
| O(n) | Linear | Linear | Array traversal |
| O(n log n) | Linearithmic | Log-linear | Efficient sorting |
| O(n²) | Quadratic | Quadratic | Nested loops, bubble sort |
| O(2ⁿ) | Exponential | Exponential | Brute-force subset search |
Interactive Tools
Wikimedia Commons, CC BY-SA
Related Terms
Time Complexity
Time complexity is a measure of the amount of time an algorithm takes to complete as a function of the size of its input, typically expressed using Big O notation. It describes how the running time grows relative to the input size, helping developers predict performance and compare algorithms. Understanding time complexity is essential for writing scalable software, especially when dealing with large datasets.
Space Complexity
Space complexity is a measure of the amount of memory an algorithm requires as a function of the size of its input, expressed in Big O notation. It includes both the memory needed to store the input (input space) and any additional auxiliary memory allocated during execution (auxiliary space). Optimising space complexity is critical in memory-constrained environments such as embedded systems or mobile devices.
Binary Search
Binary search is a highly efficient search algorithm that finds the position of a target value within a sorted array by repeatedly dividing the search interval in half. At each step, it compares the target to the middle element and discards the half in which the target cannot lie. With a time complexity of O(log n), binary search is dramatically faster than linear search for large sorted datasets.
The "O" in Big O stands for "Ordnung" (German for "order"), introduced by the German mathematician Paul Bachmann in his 1894 book "Die Analytische Zahlentheorie". It was further popularised by Edmund Landau, which is why it is also called Landau notation.