Big O measures how algorithm performance scales as input grows

Notation: O(f(n)) - upper bound on growth

Common Classes (fastest to slowest):
O(1)     - Constant time (array access, hash lookup)
O(log n) - Logarithmic (binary search)
O(n)     - Linear (simple loop through array)
O(n log n) - Linearithmic (merge sort, quick sort)
O(n²)    - Quadratic (nested loops)
O(2ⁿ)    - Exponential (recursive without memoization)
O(n!)    - Factorial (permutations)

Visual Scalability:
Input Size | O(1) | O(n) | O(n²) | O(2ⁿ)
1000       | 1    | 1K   | 1M    | 10³⁰⁰ (impossible)
10,000     | 1    | 10K  | 100M  | ∞
100,000    | 1    | 100K | 10B   | ∞

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

// O(n) - Linear time (loop once)
function findMax(arr) {
  let max = arr[0];
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] > max) max = arr[i];
  }
  return max;
}

// O(n²) - Quadratic time (nested loops)
function bubbleSort(arr) {
  for (let i = 0; i < arr.length; i++) {
    for (let j = 0; j < arr.length - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
      }
    }
  }
  return arr;
}

// O(log n) - Binary search on sorted array
function binarySearch(arr, target) {
  let left = 0, 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;
}

// O(n log n) - 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), right.slice(j));
}

Concept: Repeatedly swap adjacent elements if they're in wrong order

Process (sorting [5, 2, 8, 1]):
Pass 1: [2, 5, 1, 8] (largest bubbles to end)
Pass 2: [2, 1, 5, 8] (second largest in place)
Pass 3: [1, 2, 5, 8] (sorted)

Time Complexity:
- Best: O(n) - already sorted with optimization
- Average: O(n²)
- Worst: O(n²) - reverse order

Space: O(1) - sorts in-place

function bubbleSort(arr) {
  const n = arr.length;
  
  for (let i = 0; i < n - 1; i++) {
    let swapped = false;
    
    // Last i elements already sorted
    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]];
        swapped = true;
      }
    }
    
    // Optimization: if no swaps, already sorted
    if (!swapped) break;
  }
  
  return arr;
}

// Visualization: [5, 2, 8, 1, 9]
// Pass 1: compare 5-2, 2-8, 8-1, 1-9 → [2, 5, 1, 8, 9]
// Pass 2: compare 2-5, 5-1, 1-8 → [2, 1, 5, 8, 9]
// Pass 3: compare 2-1, 1-5 → [1, 2, 5, 8, 9]
// Done!

Concept: Find minimum, move to sorted position, repeat

Process:
1. Find minimum in unsorted portion
2. Swap with first unsorted position
3. Move boundary left
4. Repeat

Time: O(n²) always - no optimization possible
Space: O(1) - in-place

function selectionSort(arr) {
  const n = arr.length;
  
  for (let i = 0; i < n - 1; i++) {
    let minIdx = i;
    
    // Find minimum in remaining array
    for (let j = i + 1; j < n; j++) {
      if (arr[j] < arr[minIdx]) {
        minIdx = j;
      }
    }
    
    // Swap minimum to sorted position
    [arr[i], arr[minIdx]] = [arr[minIdx], arr[i]];
  }
  
  return arr;
}

Concept: Build sorted array one item at a time

Like sorting playing cards in hand:
- Take next card
- Find correct position
- Insert in sorted array
- Repeat

Time:
- Best: O(n) - already sorted
- Average: O(n²)
- Worst: O(n²)

Space: O(1) - in-place
Stable: Yes (maintains order of equal elements)

function insertionSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    const key = arr[i];
    let j = i - 1;
    
    // Find correct position for key
    while (j >= 0 && arr[j] > key) {
      arr[j + 1] = arr[j];
      j--;
    }
    
    arr[j + 1] = key;
  }
  
  return arr;
}

// Why it's good for nearly sorted data:
// [1, 2, 3, 4, 5, 0]
// 0 moves to position 0 → O(n) because mostly in order

Concept: Divide-and-conquer
1. Divide array in half recursively
2. Merge sorted halves

Time: O(n log n) - always
Space: O(n) - requires extra space
Stable: Yes

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++]);
    }
  }
  
  // Add remaining elements
  return result.concat(left.slice(i), right.slice(j));
}

// Visualization:
// [38, 27, 43, 3, 9, 82, 10]
// Divide: [38, 27, 43] | [3, 9, 82, 10]
// Divide: [38] [27, 43] | [3, 9] [82, 10]
// Merge: [27, 38, 43] | [3, 9, 10, 82]
// Merge: [3, 9, 10, 27, 38, 43, 82]

Concept: Partition-based sorting
1. Pick pivot element
2. Partition: smaller left, larger right
3. Recursively sort partitions

Time:
- Best: O(n log n) - balanced partitions
- Average: O(n log n)
- Worst: O(n²) - bad pivot choice

Space: O(log n) - recursion depth
Stable: Depends on implementation

function quickSort(arr, low = 0, high = arr.length - 1) {
  if (low < high) {
    const pi = partition(arr, low, high);
    quickSort(arr, low, pi - 1);
    quickSort(arr, pi + 1, high);
  }
  return arr;
}

function partition(arr, low, high) {
  // Pivot strategy: pick last element
  const pivot = arr[high];
  let i = low - 1;
  
  for (let j = low; j < high; j++) {
    if (arr[j] < pivot) {
      i++;
      [arr[i], arr[j]] = [arr[j], arr[i]];
    }
  }
  
  [arr[i + 1], arr[high]] = [arr[high], arr[i + 1]];
  return i + 1;
}

// Better pivot strategy: random
function partition(arr, low, high) {
  const randomIdx = low + Math.floor(Math.random() * (high - low + 1));
  [arr[randomIdx], arr[high]] = [arr[high], arr[randomIdx]];
  
  const pivot = arr[high];
  let i = low - 1;
  
  for (let j = low; j < high; j++) {
    if (arr[j] < pivot) {
      i++;
      [arr[i], arr[j]] = [arr[j], arr[i]];
    }
  }
  
  [arr[i + 1], arr[high]] = [arr[high], arr[i + 1]];
  return i + 1;
}

Time: O(n log n) - always
Space: O(1) - in-place
Stable: No (not suitable when stability needed)

function heapSort(arr) {
  const n = arr.length;
  
  // Build max heap
  for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
    heapify(arr, n, i);
  }
  
  // Extract elements from heap
  for (let i = n - 1; i > 0; i--) {
    [arr[0], arr[i]] = [arr[i], arr[0]];
    heapify(arr, i, 0);
  }
  
  return arr;
}

function heapify(arr, n, i) {
  let largest = i;
  const left = 2 * i + 1;
  const right = 2 * i + 2;
  
  if (left < n && arr[left] > arr[largest]) largest = left;
  if (right < n && arr[right] > arr[largest]) largest = right;
  
  if (largest !== i) {
    [arr[i], arr[largest]] = [arr[largest], arr[i]];
    heapify(arr, n, largest);
  }
}

Non-comparison sort: sorts by individual digits

Time: O(d * n) where d = number of digits
Space: O(n + k) where k = range of digits
Great for: Integers, strings of fixed length

Example: Sorting [170, 45, 75, 90, 2, 802, 24, 2, 66]

Least Significant Digit (LSD) approach:
1. Sort by ones place
2. Sort by tens place
3. Sort by hundreds place
...

Result: [2, 2, 24, 45, 66, 75, 90, 170, 802]

function radixSort(arr) {
  const max = Math.max(...arr);
  let exp = 1;
  
  while (Math.floor(max / exp) > 0) {
    countingSortByDigit(arr, exp);
    exp *= 10;
  }
  
  return arr;
}

function countingSortByDigit(arr, exp) {
  const n = arr.length;
  const output = new Array(n);
  const count = new Array(10).fill(0);
  
  for (let i = 0; i < n; i++) {
    const digit = Math.floor((arr[i] / exp) % 10);
    count[digit]++;
  }
  
  for (let i = 1; i < 10; i++) {
    count[i] += count[i - 1];
  }
  
  for (let i = n - 1; i >= 0; i--) {
    const digit = Math.floor((arr[i] / exp) % 10);
    output[count[digit] - 1] = arr[i];
    count[digit]--;
  }
  
  for (let i = 0; i < n; i++) {
    arr[i] = output[i];
  }
}

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

// Use when: Array unsorted or small
// Time: O(n) - worst case entire array

Prerequisite: Array must be sorted

Concept: Eliminate half of remaining elements each iteration

Time: O(log n) - 1M items = 20 comparisons max
Space: O(1) for iterative, O(log n) for recursive

// Iterative (more efficient)
function binarySearch(arr, target) {
  let left = 0, 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; // Not found
}

// Recursive
function binarySearchRec(arr, target, left = 0, right = arr.length - 1) {
  if (left > right) return -1;
  
  const mid = Math.floor((left + right) / 2);
  
  if (arr[mid] === target) return mid;
  if (arr[mid] < target) return binarySearchRec(arr, target, mid + 1, right);
  return binarySearchRec(arr, target, left, mid - 1);
}

// Variations:
// Find leftmost position: bisect_left
// Find rightmost position: bisect_right
// Check if exists: Any binary search variant

Algorithm      | Best    | Average | Worst   | Space | Stable
Bubble Sort    | O(n)    | O(n²)   | O(n²)   | O(1)  | Yes
Selection Sort | O(n²)   | O(n²)   | O(n²)   | O(1)  | No
Insertion Sort | O(n)    | O(n²)   | O(n²)   | O(1)  | Yes
Merge Sort     | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes
Quick Sort     | O(n log n) | O(n log n) | O(n²)   | O(log n) | No
Heap Sort      | O(n log n) | O(n log n) | O(n log n) | O(1) | No
Radix Sort     | O(dn)   | O(dn)   | O(dn)   | O(n+k) | Yes

Arrays of 1000 elements (average case, milliseconds):
Bubble Sort: 15ms
Selection Sort: 12ms
Insertion Sort: 3ms (nearly sorted data)
Merge Sort: 0.5ms
Quick Sort: 0.1ms
Radix Sort: 0.08ms

Key insights:
- O(n²) not acceptable for n > 10,000
- Quick sort 100x faster than bubble sort
- For nearly sorted: insertion sort competitive
- For production: use language built-in (highly optimized)

// Given array with 0, 1, 2 → sort in-place
// Input: [2, 0, 2, 1, 1, 0]
// Output: [0, 0, 1, 1, 2, 2]

// Approach: Dutch National Flag (3-way partition)
function sortColors(nums) {
  let left = 0, mid = 0, right = nums.length - 1;
  
  while (mid <= right) {
    if (nums[mid] === 0) {
      [nums[left], nums[mid]] = [nums[mid], nums[left]];
      left++;
      mid++;
    } else if (nums[mid] === 1) {
      mid++;
    } else { // nums[mid] === 2
      [nums[mid], nums[right]] = [nums[right], nums[mid]];
      right--;
    }
  }
  
  return nums;
}

// Time: O(n), Space: O(1)

// Input: [[1, 4, 5], [1, 3, 4], [2, 6]]
// Output: [1, 1, 2, 3, 4, 4, 5, 6]

// Approach: Min Heap (Priority Queue)
class MinHeap {
  constructor() {
    this.heap = [];
  }
  
  push(val) {
    this.heap.push(val);
    this.bubbleUp(this.heap.length - 1);
  }
  
  pop() {
    if (this.heap.length === 0) return null;
    const min = this.heap[0];
    const last = this.heap.pop();
    if (this.heap.length > 0) {
      this.heap[0] = last;
      this.bubbleDown(0);
    }
    return min;
  }
  
  bubbleUp(idx) {
    while (idx > 0) {
      const parentIdx = Math.floor((idx - 1) / 2);
      if (this.heap[parentIdx] > this.heap[idx]) {
        [this.heap[parentIdx], this.heap[idx]] = [this.heap[idx], this.heap[parentIdx]];
        idx = parentIdx;
      } else break;
    }
  }
  
  bubbleDown(idx) {
    while (2 * idx + 1 < this.heap.length) {
      let smallerIdx = 2 * idx + 1;
      if (2 * idx + 2 < this.heap.length && this.heap[2 * idx + 2] < this.heap[smallerIdx]) {
        smallerIdx = 2 * idx + 2;
      }
      if (this.heap[smallerIdx] < this.heap[idx]) {
        [this.heap[smallerIdx], this.heap[idx]] = [this.heap[idx], this.heap[smallerIdx]];
        idx = smallerIdx;
      } else break;
    }
  }
}

function mergeKLists(lists) {
  const heap = new MinHeap();
  const result = [];
  
  for (let i = 0; i < lists.length; i++) {
    if (lists[i].length > 0) {
      heap.push([lists[i][0], i, 0]);
    }
  }
  
  while (heap.heap.length > 0) {
    const [val, listIdx, elemIdx] = heap.pop();
    result.push(val);
    
    if (elemIdx + 1 < lists[listIdx].length) {
      heap.push([lists[listIdx][elemIdx + 1], listIdx, elemIdx + 1]);
    }
  }
  
  return result;
}

// Time: O(n log k) where n = total elements, k = number of lists
// Space: O(k) for heap

// Fibonacci - Exponential without optimization
function fib(n) {
  if (n <= 1) return n;
  return fib(n - 1) + fib(n - 2);
}
// fib(40) = 26 seconds (exponential explosion!)

// With Memoization - O(n)
function fibMemo(n, memo = {}) {
  if (n in memo) return memo[n];
  if (n <= 1) return n;
  
  memo[n] = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
  return memo[n];
}
// fib(40) = instant!

// Lesson: Memoization caches results, eliminates redundant work