jsschools

Big-O Notation (O)

An asymptotic upper bound describing the worst-case growth rate of an algorithm's resource usage as input size n tends to infinity.

Spec ↗

Syntax

f(n) = O(g(n))
// iff ∃ constants c > 0, n₀ > 0 such that
// f(n) ≤ c·g(n) for all n ≥ n₀

Parameters

NameTypeRequiredDescription
f(n) function Yes The actual runtime or space usage of the algorithm.
g(n) function Yes The bounding function (e.g., n², n log n, n).

Returns

boolean — True if f is asymptotically bounded above by g.

Examples

// O(1) — constant time
function getFirst(arr) { return arr[0]; }

// O(n) — linear time
function linearSearch(arr, target) {
  for (const x of arr) if (x === target) return true;
  return false;
}

// O(n²) — quadratic time (bubble sort inner loop)
function bubbleSort(arr) {
  const a = [...arr];
  for (let i = 0; i < a.length; i++)
    for (let j = 0; j < a.length - i - 1; j++)
      if (a[j] > a[j+1]) [a[j], a[j+1]] = [a[j+1], a[j]];
  return a;
}

const sizes = [1_000, 10_000, 100_000];
sizes.forEach(n => {
  const arr = Array.from({ length: n }, () => Math.random());
  const t = performance.now();
  linearSearch(arr, -1);
  console.log(`O(n): n=${n} ~${(performance.now()-t).toFixed(2)}ms`);
});
Output 
O(n): n=1000 ~0.05ms
O(n): n=10000 ~0.42ms
O(n): n=100000 ~4.10ms

// Common complexity classes, fastest to slowest:
const complexities = [
  ['O(1)',       'Hash table lookup'],
  ['O(log n)',   'Binary search'],
  ['O(n)',       'Linear scan'],
  ['O(n log n)', 'Merge sort'],
  ['O(n²)',      'Bubble sort'],
  ['O(2ⁿ)',      'All subsets'],
  ['O(n!)',      'All permutations'],
];
complexities.forEach(([c, ex]) => console.log(`${c.padEnd(12)} ${ex}`));
Output 
O(1)         Hash table lookup
O(log n)     Binary search
O(n)         Linear scan
O(n log n)   Merge sort
O(n²)        Bubble sort
O(2ⁿ)        All subsets
O(n!)        All permutations

Notes

Big-O gives an *upper* bound — it says "the algorithm runs no worse than this". It intentionally drops constant factors and lower-order terms: O(3n + 100) = O(n). Hierarchy (for large n): O(1) < O(log n) < O(√n) < O(n) < O(n log n) < O(n²) < O(n³) < O(2ⁿ) < O(n!) Practical rules of thumb (LeetCode / competitive programming): - n ≤ 10: O(n!) ok - n ≤ 20: O(2ⁿ) ok - n ≤ 500: O(n³) ok - n ≤ 5,000: O(n²) ok - n ≤ 10⁶: O(n log n) ok - n ≤ 10⁸: O(n) ok

See also