Big O Notation - Complete Guide

Big O notation describes the performance and complexity of algorithms. This guide covers everything you need to understand algorithmic efficiency.

What is Big O Notation? #

Big O notation describes how an algorithm’s runtime or space requirements grow as the input size increases. It answers: “How does performance scale?”

Common Time Complexities #

O(1) - Constant Time #

Performance doesn’t depend on input size.

function getFirst(array) {
  return array[0];  // Always one operation
}

function addToHash(map, key, value) {
  map.set(key, value);  // Constant time
}

Examples: Array access, hash table insertion/lookup

O(log n) - Logarithmic Time #

Divides problem in half each step.

function binarySearch(arr, target) {
  let left = 0;
  let right = arr.length - 1;

  while (left <= right) {
    const mid = Math.floor((left + right) / 2);

    if (arr[mid] === target) return mid;
    if (arr[mid] < target) left = mid + 1;
    else right = mid - 1;
  }

  return -1;
}

Examples: Binary search, balanced tree operations

O(n) - Linear Time #

Iterates through all elements once.

function findMax(array) {
  let max = array[0];

  for (let i = 1; i < array.length; i++) {
    if (array[i] > max) {
      max = array[i];
    }
  }

  return max;
}

Examples: Linear search, array traversal

O(n log n) - Linearithmic Time #

Efficient sorting algorithms.

function mergeSort(arr) {
  if (arr.length <= 1) return arr;

  const mid = Math.floor(arr.length / 2);
  const left = mergeSort(arr.slice(0, mid));
  const right = mergeSort(arr.slice(mid));

  return merge(left, right);
}

Examples: Merge sort, quicksort (average), heap sort

O(n²) - Quadratic Time #

Nested loops over input.

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]];
      }
    }
  }
  return arr;
}

Examples: Bubble sort, selection sort, nested iteration

O(2^n) - Exponential Time #

Doubles with each additional input.

function fibonacci(n) {
  if (n <= 1) return n;
  return fibonacci(n - 1) + fibonacci(n - 2);
}

Examples: Naive recursive Fibonacci, subsets generation

O(n!) - Factorial Time #

Generates all permutations.

function permutations(arr) {
  if (arr.length <= 1) return [arr];

  const result = [];
  for (let i = 0; i < arr.length; i++) {
    const current = arr[i];
    const remaining = arr.slice(0, i).concat(arr.slice(i + 1));
    const perms = permutations(remaining);

    for (const perm of perms) {
      result.push([current, ...perm]);
    }
  }

  return result;
}

Examples: Generating permutations, traveling salesman

Complexity Comparison #

Big ONameExampleOperations for n=10
O(1)ConstantArray access1
O(log n)LogarithmicBinary search3
O(n)LinearLoop10
O(n log n)LinearithmicMerge sort33
O(n²)QuadraticNested loops100
O(2^n)ExponentialFibonacci1,024
O(n!)FactorialPermutations3,628,800

Space Complexity #

Measures memory usage.

O(1) Space #

function sum(arr) {
  let total = 0;  // Fixed variables
  for (const num of arr) {
    total += num;
  }
  return total;
}

O(n) Space #

function double(arr) {
  const result = [];  // New array of size n
  for (const num of arr) {
    result.push(num * 2);
  }
  return result;
}

O(n²) Space #

function create2DArray(n) {
  const matrix = [];
  for (let i = 0; i < n; i++) {
    matrix[i] = new Array(n).fill(0);
  }
  return matrix;
}

Analyzing Algorithms #

Drop Constants #

// O(2n) → O(n)
function example(arr) {
  arr.forEach(x => console.log(x));  // O(n)
  arr.forEach(x => console.log(x));  // O(n)
}
// Total: O(2n) = O(n)

Drop Non-Dominant Terms #

// O(n² + n) → O(n²)
function example(arr) {
  // O(n)
  for (let i = 0; i < arr.length; i++) {
    console.log(arr[i]);
  }

  // O(n²)
  for (let i = 0; i < arr.length; i++) {
    for (let j = 0; j < arr.length; j++) {
      console.log(arr[i], arr[j]);
    }
  }
}
// Total: O(n + n²) = O(n²)

Multiple Inputs #

// O(a + b)
function merge(arr1, arr2) {
  for (const x of arr1) console.log(x);  // O(a)
  for (const y of arr2) console.log(y);  // O(b)
}

// O(a * b)
function pairs(arr1, arr2) {
  for (const x of arr1) {
    for (const y of arr2) {
      console.log(x, y);
    }
  }
}

Best, Average, Worst Case #

function search(arr, target) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === target) return i;
  }
  return -1;
}

// Best case: O(1) - target at index 0
// Average case: O(n/2) = O(n)
// Worst case: O(n) - target not found or at end

Recursive Complexity #

Single Recursive Call #

function factorial(n) {
  if (n <= 1) return 1;
  return n * factorial(n - 1);
}
// Time: O(n), Space: O(n) for call stack

Multiple Recursive Calls #

function fibonacci(n) {
  if (n <= 1) return n;
  return fibonacci(n - 1) + fibonacci(n - 2);
}
// Time: O(2^n), Space: O(n) for call stack depth

With Memoization #

function fibonacci(n, memo = {}) {
  if (n in memo) return memo[n];
  if (n <= 1) return n;

  memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo);
  return memo[n];
}
// Time: O(n), Space: O(n)

Common Patterns #

Two Pointers #

function twoSum(arr, target) {
  let left = 0;
  let right = arr.length - 1;

  while (left < right) {
    const sum = arr[left] + arr[right];
    if (sum === target) return [left, right];
    if (sum < target) left++;
    else right--;
  }

  return [];
}
// Time: O(n), Space: O(1)

Sliding Window #

function maxSum(arr, k) {
  let windowSum = 0;
  let maxSum = 0;

  for (let i = 0; i < k; i++) {
    windowSum += arr[i];
  }

  maxSum = windowSum;

  for (let i = k; i < arr.length; i++) {
    windowSum = windowSum - arr[i - k] + arr[i];
    maxSum = Math.max(maxSum, windowSum);
  }

  return maxSum;
}
// Time: O(n), Space: O(1)

Hash Table #

function hasDuplicate(arr) {
  const seen = new Set();

  for (const num of arr) {
    if (seen.has(num)) return true;
    seen.add(num);
  }

  return false;
}
// Time: O(n), Space: O(n)

Optimization Examples #

Example 1: Find Pair Sum #

Brute Force O(n²):

function hasPairSum(arr, target) {
  for (let i = 0; i < arr.length; i++) {
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[i] + arr[j] === target) return true;
    }
  }
  return false;
}

Optimized O(n):

function hasPairSum(arr, target) {
  const seen = new Set();

  for (const num of arr) {
    if (seen.has(target - num)) return true;
    seen.add(num);
  }

  return false;
}

Example 2: Find Duplicates #

Brute Force O(n²):

function findDuplicates(arr) {
  const duplicates = [];

  for (let i = 0; i < arr.length; i++) {
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[i] === arr[j] && !duplicates.includes(arr[i])) {
        duplicates.push(arr[i]);
      }
    }
  }

  return duplicates;
}

Optimized O(n):

function findDuplicates(arr) {
  const seen = new Set();
  const duplicates = new Set();

  for (const num of arr) {
    if (seen.has(num)) {
      duplicates.add(num);
    }
    seen.add(num);
  }

  return Array.from(duplicates);
}

Practical Tips #

  1. Start with brute force - Get working solution first
  2. Identify bottlenecks - Where is time spent?
  3. Consider tradeoffs - Time vs space
  4. Use appropriate data structures - Hash tables for lookups
  5. Think about edge cases - Empty input, single element
  6. Optimize when needed - Don’t prematurely optimize
  7. Measure actual performance - Big O is theoretical

Common Mistakes #

  1. Ignoring hidden costs - Array copying in slice()
  2. Confusing best/worst case - Be clear which you’re discussing
  3. Forgetting space complexity - Memory matters too
  4. Over-optimizing - Readable code often more valuable
  5. Not considering input size - What’s n in your problem?

Understanding Big O notation helps you write efficient algorithms and make informed decisions about data structures and approaches.

Previous Object-Oriented Programming Concepts Complete Guide to REST APIs Next