Skip to content

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

javascript
// 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));    // 1000000

For n=1000, the gap between growth rates is dramatic. Big O captures this asymptotic difference, ignoring constants.

Related terms

Related Resources

Related Lessons

Decode error messages

Plain-English explanations of common errors — what they mean, why they happen, and how to fix them.

View errors

← Back to glossary