Big O Notation
In one line
Big O notation describes how an algorithm's runtime or memory grows relative to input size, ignoring constants.
In simple words
Big O notation is a mathematical way to describe the worst-case growth rate of an algorithm as the input size (n) grows toward infinity. It focuses on the dominant term and ignores constant factors and lower-order terms, giving you a way to compare algorithms at a glance.
Common growth rates from fastest to slowest: O(1) constant (hash lookup), O(log n) logarithmic (binary search), O(n) linear (single loop), O(n log n) linearithmic (good sorts), O(n²) quadratic (nested loops), O(2^n) exponential (naive recursion). An O(n log n) algorithm will always beat an O(n²) one for large enough n, regardless of constant factors.
Big O helps you reason about scalability. An O(n²) algorithm that handles 100 items in 1ms would take 100ms for 1000 items and 10 seconds for 10000 — the growth rate, not the absolute speed, determines how your code scales. Big Omega (Ω) is the lower bound and Big Theta (Θ) is a tight bound; Big O is the upper bound and the most commonly used.
Example
// Comparing growth rates
function constant(n) { return 1; } // O(1)
function logarithmic(n) { return Math.log2(n); } // O(log n)
function linear(n) { return n; } // O(n)
function quadratic(n) { return n * n; } // O(n^2)
const n = 1000;
console.log("O(1): ", constant(n)); // 1
console.log("O(log n): ", logarithmic(n)); // ~10
console.log("O(n): ", linear(n)); // 1000
console.log("O(n^2): ", quadratic(n)); // 1000000For n=1000, the gap between growth rates is dramatic. Big O captures this asymptotic difference, ignoring constants.
Related terms
Related Resources
Related Lessons
- Algorithms
Learn Big O and complexity analysis.
Decode error messages
Plain-English explanations of common errors — what they mean, why they happen, and how to fix them.