Big O Notation

What is Big O Notation?

Big O notation is a mathematical notation used to describe the performance or complexity of an algorithm. It specifically describes the worst-case scenario and helps us understand how the runtime or space requirements grow as the input size increases.

Big O notation gives us a high-level understanding of the time or space complexity of an algorithm, allowing us to compare different approaches and choose the most efficient one.

Common Time Complexities

Here are the most common Big O complexities, ordered from best to worst:

// Example: Array access by index
function getFirstElement(arr) {
  return arr[0]; // Always takes the same time
}

// Example: Hash table lookup
const map = new Map([['key', 'value']]);
map.get('key'); // O(1) lookup

// Example: Binary search
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;
}

// With each iteration, we cut the search space in half
// For 1000 items, only ~10 comparisons needed!

// Example: Finding max in unsorted array
function findMax(arr) {
  let max = arr[0];
  
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] > max) {
      max = arr[i];
    }
  }
  
  return max;
}

// Must check every element once

// Example: Merge Sort
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);
}

function merge(left, right) {
  const result = [];
  let i = 0, j = 0;
  
  while (i < left.length && j < right.length) {
    if (left[i] < right[j]) {
      result.push(left[i++]);
    } else {
      result.push(right[j++]);
    }
  }
  
  return result.concat(left.slice(i)).concat(right.slice(j));
}

// Example: Bubble Sort
function bubbleSort(arr) {
  const n = arr.length;
  
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
      }
    }
  }
  
  return arr;
}

// For 1000 items, this makes ~1,000,000 comparisons!

// Example: Naive Fibonacci (inefficient)
function fibonacci(n) {
  if (n <= 1) return n;
  return fibonacci(n - 1) + fibonacci(n - 2);
}

// Exponential growth - fibonacci(50) would take years!
// This is why we need dynamic programming

Big O Complexity Chart

Space Complexity

Big O also describes space (memory) complexity. It measures how much additional memory an algorithm needs.

// Uses fixed amount of space
function sum(a, b) {
  return a + b; // No extra space
}

// Creates new array
function double(arr) {
  const result = [];
  for (let i = 0; i < arr.length; i++) {
    result.push(arr[i] * 2);
  }
  return result;
}

Big O, Big Omega, and Big Theta

Rules for Calculating Big O

// This is O(n), not O(2n)
function example(arr) {
  for (let i = 0; i < arr.length; i++) { } // O(n)
  for (let i = 0; i < arr.length; i++) { } // O(n)
  // Total: O(n + n) = O(2n) = O(n)
}

// This is O(n²), not O(n² + n)
function example(arr) {
  for (let i = 0; i < arr.length; i++) { } // O(n)
  
  for (let i = 0; i < arr.length; i++) {
    for (let j = 0; j < arr.length; j++) { } // O(n²)
  }
  // Total: O(n + n²) = O(n²)
}

// This is O(a + b), not O(n)
function example(arr1, arr2) {
  for (let i = 0; i < arr1.length; i++) { } // O(a)
  for (let i = 0; i < arr2.length; i++) { } // O(b)
  // Total: O(a + b)
}