Big O Notation Explained Without Math — A Developer's Visual Guide

const arr = [10, 20, 30, 40, 50];

// Array index lookup — always 1 operation, no matter array size
const first = arr[0];    // O(1)
const last = arr[arr.length - 1];  // O(1)

// Object property access — hash table lookup
const user = { name: 'Alice', role: 'admin' };
const name = user.name;  // O(1)

// Hash map lookup (average case)
const map = new Map([['alice', { age: 30 }]]);
const alice = map.get('alice');  // O(1)

// Math operations — constant regardless of number size
const area = Math.PI * radius * radius;  // O(1)
const isEven = n => n % 2 === 0;        // O(1)

// Stack push/pop — O(1) amortized
const stack = [];
stack.push(42);  // O(1)
stack.pop();     // O(1)

// All O(1) — doesn't matter if the collection has 10 or 10,000,000 elements
// The key: direct computation or direct address access, no traversal

// Single loop — visit every element once
function findMax(arr) {
  let max = arr[0];
  for (const n of arr) {   // n iterations — can't skip any element
    if (n > max) max = n;
  }
  return max;
}

// Multiple separate passes are STILL O(n) — not O(2n):
function minAndMax(arr) {
  let min = Infinity, max = -Infinity;
  for (const x of arr) min = Math.min(min, x);  // pass 1: O(n)
  for (const x of arr) max = Math.max(max, x);  // pass 2: O(n)
  return { min, max };  // Total: O(2n) = O(n) — constants drop
}

// Array built-in methods — all O(n) (they loop internally):
arr.forEach(x => ...)    // O(n) — visits every element
arr.map(x => x * 2)     // O(n) — creates new array of same size
arr.filter(x => x > 0)  // O(n) — worst case visits all
arr.find(x => x > 5)    // O(n) — worst case visits all
arr.reduce(...)          // O(n)
arr.includes(42)         // O(n) — linear scan!
arr.indexOf(42)          // O(n) — linear scan!

// String operations are also O(n):
str.includes('x')        // O(n)
str.split(',')           // O(n)
JSON.stringify(obj)      // O(n) where n = number of keys/values

// Pattern 1: Classic nested loops
function bubbleSort(arr) {
  for (let i = 0; i < arr.length; i++) {       // n times
    for (let j = 0; j < arr.length - 1; j++) { // n times each = O(n²)
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
      }
    }
  }
}
// Use arr.sort() instead — O(n log n), always

// Pattern 2: arr.includes() inside a loop
function hasAllItems(arr, required) {
  return required.every(item => arr.includes(item));  // O(n²): O(n) × O(n)
}
// Fix: const set = new Set(arr); required.every(item => set.has(item)); — O(n)

// Pattern 3: Cartesian product (sometimes unavoidable)
function allPairs(arr) {
  const pairs = [];
  for (let i = 0; i < arr.length; i++) {
    for (let j = i + 1; j < arr.length; j++) {
      pairs.push([arr[i], arr[j]]);
    }
  }
  return pairs;  // Must generate n(n-1)/2 pairs — O(n²) is unavoidable
}

// Key question to ask: "Is the inner loop size dependent on n?"
// If yes: O(n²). If inner loop has a fixed bound: still O(n).

// Binary search on sorted array — halves the search space each step
function binarySearch(sortedArr, target) {
  let low = 0, high = sortedArr.length - 1;

  while (low <= high) {           // runs at most log₂(n) times
    const mid = (low + high) >> 1;  // bitwise divide by 2, no overflow
    if (sortedArr[mid] === target) return mid;
    if (sortedArr[mid] < target) low = mid + 1;
    else high = mid - 1;
  }

  return -1;  // not found
}

// Why O(log n)? Each step:
// n=1,000,000 → step 1: 500,000 left
// n=1,000,000 → step 2: 250,000 left
// n=1,000,000 → step 3: 125,000 left
// ...step 20: 1 left — found! log₂(1,000,000) ≈ 20

// Other O(log n) operations:
// - TreeMap / SortedMap lookups (balanced BST)
// - Binary heap insert/extract (priority queue)
// - Math.pow(base, exponent) with fast exponentiation
// - Segment tree queries

// JavaScript's Set.has() and Map.get() are O(1) average (hash table)
// but TreeMap / SortedDict (if using a library) are O(log n)

// JavaScript's built-in sort — O(n log n) always (TimSort)
const arr = [5, 2, 8, 1, 9, 3];
arr.sort((a, b) => a - b);  // O(n log n) — always safe to use

// Why is merge sort O(n log n)?
// - Divide: split into halves (log n levels deep — like a tree)
// - Conquer: merge each level (O(n) total work per level)
// - Total: O(n) × O(log n levels) = O(n log n)

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

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

  return merge(left, right);  // O(n) merge work at each level
}

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, ...left.slice(i), ...right.slice(j)];
}

// Visualization for n=8:
// Level 0: [5,2,8,1,9,3,7,4]              — 1 array, n=8 total work to merge
// Level 1: [5,2,8,1] [9,3,7,4]            — 2 arrays, n=8 total work to merge
// Level 2: [5,2][8,1] [9,3][7,4]          — 4 arrays, n=8 total work to merge
// Level 3: [5][2][8][1][9][3][7][4]       — 8 base cases
// log₂(8) = 3 levels × O(n=8) work per level = O(8 × 3) = O(n log n)