Big-O notation

Big-O notation describes how the cost of an algorithm (in time or memory) grows as the size of the input n increases. It ignores constants and lower-order terms to focus on large-scale behavior.

Common complexities (from best to worst)

Notation	Name	Example
`O(1)`	Constant	Accessing `arr[0]`
`O(log n)`	Logarithmic	Binary search
`O(n)`	Linear	Iterating over an array
`O(n log n)`	Linearithmic	Merge sort, quick sort
`O(n²)`	Quadratic	Bubble sort, nested loops
`O(2ⁿ)`	Exponential	Naive recursive Fibonacci

Examples

// O(1): does not depend on the size
function first(arr) {
  return arr[0];
}

// O(n): one pass over the array
function sum(arr) {
  let total = 0;
  for (const x of arr) total += x;
  return total;
}

// O(n²): one loop inside another
function pairs(arr) {
  const output = [];
  for (const a of arr) {
    for (const b of arr) {
      output.push([a, b]);
    }
  }
  return output;
}

The rule of thumb: count the loops nested over the input. Two loops nested over n are usually O(n²).

Examples

Compare the number of operations

function linearOperations(n) {
  let ops = 0;
  for (let i = 0; i < n; i++) ops++;
  return ops;
}
function quadraticOperations(n) {
  let ops = 0;
  for (let i = 0; i < n; i++)
    for (let j = 0; j < n; j++) ops++;
  return ops;
}
console.log("Linear n=10:", linearOperations(10));
console.log("Quadratic n=10:", quadraticOperations(10));