Algorithms Lesson 1: Big O Notation

Big O notation describes how an algorithm’s performance scales with input size. Every coding interview includes Big O questions. Every professional developer thinks in Big O.

Common Complexities

// O(1) — Constant: same speed regardless of input size
function getFirst(arr) { return arr[0]; }         // always 1 step
function addToHashMap(map, key, val) { map[key] = val; } // O(1) average

// O(log n) — Logarithmic: halves problem each step (VERY FAST)
// Binary search on sorted array of 1M items = 20 steps!

// O(n) — Linear: scales with input
function findMax(arr) {
  let max = -Infinity;
  for (const n of arr) if (n > max) max = n; // visits every element
  return max;
}

// O(n log n) — Best for sorting (mergesort, quicksort)
// O(n²) — Quadratic: nested loops (SLOW for large inputs)
function bubbleSort(arr) {
  for (let i = 0; i < arr.length; i++)
    for (let j = 0; j < arr.length - i - 1; j++)
      if (arr[j] > arr[j+1]) [arr[j], arr[j+1]] = [arr[j+1], arr[j]];
}

// O(2^n) — Exponential: AVOID! Doubles with each element
// O(n!) — Factorial: VERY AVOID! (traveling salesman brute force)

Analyzing Code

function analyze(arr) {
  const n = arr.length;
  
  console.log(arr[0]);           // O(1) — constant
  
  for (let i = 0; i < n; i++) { // O(n) — linear loop
    console.log(arr[i]);
  }
  
  for (let i = 0; i < n; i++) { // O(n²) — nested loops
    for (let j = 0; j < n; j++) {
      console.log(arr[i], arr[j]);
    }
  }
}
// Total: O(1) + O(n) + O(n²) = O(n²) (keep the dominant term)

Space Complexity

// O(1) space: no extra memory proportional to input
function sum(arr) {
  let total = 0;          // just one variable
  for (const n of arr) total += n;
  return total;
}

// O(n) space: stores copy of input
function double(arr) {
  return arr.map(x => x * 2); // creates new array of size n
}