function countOps(arr) {
  let total = 0               // 1 assignment
  for (let i = 0; i < arr.length; i++) {  // n iterations of the loop body
    total += arr[i]           // 1 read + 1 addition + 1 assignment = 3 ops
    total *= 2                // 1 multiply + 1 assignment = 2 ops
  }
  return total                // 1 return
}
// Exact count: 1 + n×5 + 1 = 5n + 2
// Big O: O(n)  (drop constant 5 and lower-order term 2)

// Standard O(n) — each iteration: O(1) work
function sumArray(arr) {
  let sum = 0
  for (let i = 0; i < arr.length; i++) {  // n iterations
    sum += arr[i]
  }
  return sum  // O(n)
}

// O(n/2) = O(n) — halving the range doesn't change the class
function sumEvenIndices(arr) {
  let sum = 0
  for (let i = 0; i < arr.length; i += 2) {  // n/2 iterations
    sum += arr[i]
  }
  return sum  // O(n/2) = O(n)
}

// O(log n) — halving the counter, not the range
function countHalving(n) {
  let count = 0
  while (n > 1) {
    n = Math.floor(n / 2)  // halve n each step
    count++
  }
  return count  // O(log n)
}

// O(n) — even though it looks like it counts down
function countdown(n) {
  for (let i = n; i > 0; i--) {  // still n iterations
    console.log(i)
  }  // O(n)
}

// Both loops run n times — O(n × n) = O(n²)
function printAllPairs(arr) {
  for (let i = 0; i < arr.length; i++) {      // n iterations
    for (let j = 0; j < arr.length; j++) {    // n iterations each time
      console.log(arr[i], arr[j])
    }
  }
}

// Inner loop shrinks: j from i+1 to n
// Total iterations: n(n-1)/2 ≈ n²/2 — still O(n²)
function printUniquePairs(arr) {
  for (let i = 0; i < arr.length; i++) {
    for (let j = i + 1; j < arr.length; j++) {
      console.log(arr[i], arr[j])
    }
  }
}

// Inner loop always runs exactly 3 times — O(3n) = O(n)
function fixedInner(arr) {
  for (let i = 0; i < arr.length; i++) {  // n iterations
    for (let k = 0; k < 3; k++) {         // always 3 — constant!
      console.log(arr[i], k)
    }
  }
}

// Triple nested loop — O(n³)
function triplePrint(n) {
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      for (let k = 0; k < n; k++) {
        console.log(i, j, k)
      }
    }
  }
}

function sequentialLoops(arr, matrix) {
  // Section 1: O(n)
  let sum = 0
  for (const x of arr) sum += x

  // Section 2: O(n) — still just adds to O(n)
  let max = -Infinity
  for (const x of arr) if (x > max) max = x

  // Section 3: O(n²) — matrix is n×n
  let total = 0
  for (const row of matrix)
    for (const cell of row)
      total += cell

  return { sum, max, total }
  // Total: O(n) + O(n) + O(n²) = O(2n + n²) = O(n²)
}

// Another example: O(n) + O(n log n) = O(n log n)
function sortAndScan(arr) {
  arr.sort()                           // O(n log n)
  let count = 0
  for (const x of arr) if (x > 0) count++  // O(n)
  return count
  // Total: O(n log n + n) = O(n log n)
}

// Calling sort() inside a loop: O(n) × O(n log n) = O(n² log n)
function sortedMax(matrix) {
  const results = []
  for (const row of matrix) {          // n rows
    const sorted = [...row].sort()     // O(n log n) per row!
    results.push(sorted[sorted.length - 1])
  }
  return results
  // Total: O(n × n log n) = O(n² log n)
}

// Better: find max without sorting — O(n) total
function fastMax(matrix) {
  return matrix.map(row => Math.max(...row))  // O(n) per row × n rows = O(n²)
}

// indexOf() is O(n) — calling inside a loop makes it O(n²)!
function hasDuplicatesSlow(arr) {
  for (let i = 0; i < arr.length; i++) {
    if (arr.indexOf(arr[i]) !== i) return true  // indexOf is O(n)!
  }
  return false  // Total: O(n²)
}

// Better: hash set — O(n) total
function hasDuplicatesFast(arr) {
  const seen = new Set()
  for (const x of arr) {
    if (seen.has(x)) return true
    seen.add(x)
  }
  return false  // O(n)
}

// Linear recursion: T(n) = T(n-1) + O(1) → O(n)
function factorial(n) {
  if (n <= 1) return 1
  return n * factorial(n - 1)  // 1 recursive call, O(1) work
}
// T(n) = T(n-1) + 1 = T(n-2) + 2 = ... = T(1) + n-1 = O(n)

// Binary recursion: T(n) = 2T(n/2) + O(n) → O(n log n)
function mergeSort(arr) {
  if (arr.length <= 1) return arr
  const mid = Math.floor(arr.length / 2)
  const L = mergeSort(arr.slice(0, mid))   // T(n/2)
  const R = mergeSort(arr.slice(mid))      // T(n/2)
  return merge(L, R)                       // O(n) merge
}
// By Master Theorem: T(n) = 2T(n/2) + O(n) → O(n log n)

// Binary recursion with O(1) work: T(n) = 2T(n/2) + O(1) → O(n)
function countNodes(root) {
  if (!root) return 0
  return 1 + countNodes(root.left) + countNodes(root.right)
  // Visits every node once: O(n) total
}

// Exponential recursion: T(n) = 2T(n-1) + O(1) → O(2ⁿ)
function fibSlow(n) {
  if (n <= 1) return n
  return fibSlow(n - 1) + fibSlow(n - 2)  // 2 calls, each size n-1 and n-2
}

// Reversing a string — O(n)
function reverse(s) {
  return s.split('').reverse().join('')
  // split: O(n), reverse: O(n), join: O(n)
  // Total: O(3n) = O(n)
}

// Checking if two strings are anagrams — O(n)
function isAnagram(s, t) {
  if (s.length !== t.length) return false
  const freq = {}
  for (const ch of s) freq[ch] = (freq[ch] || 0) + 1  // O(n)
  for (const ch of t) {                                 // O(n)
    if (!freq[ch]) return false
    freq[ch]--
  }
  return true  // O(n) total
}

// Longest unique substring — sliding window O(n)
function lengthOfLongestSubstring(s) {
  const seen = new Set()
  let left = 0, maxLen = 0
  for (let right = 0; right < s.length; right++) {  // right pointer: n moves
    while (seen.has(s[right])) {
      seen.delete(s[left++])  // left pointer: at most n moves total
    }
    seen.add(s[right])
    maxLen = Math.max(maxLen, right - left + 1)
  }
  return maxLen
  // Both pointers move at most n times total: O(n)
}

// Naive substring search — O(n × m)
function naiveSearch(text, pattern) {
  for (let i = 0; i <= text.length - pattern.length; i++) {  // O(n)
    let match = true
    for (let j = 0; j < pattern.length; j++) {               // O(m)
      if (text[i + j] !== pattern[j]) { match = false; break }
    }
    if (match) return i
  }
  return -1
  // O(n × m) — use KMP for O(n + m)
}

// Inorder traversal — O(n): visits every node exactly once
function inorder(root, result = []) {
  if (!root) return result
  inorder(root.left, result)
  result.push(root.val)
  inorder(root.right, result)
  return result
}

// Height of a binary tree — O(n): visits every node
function height(root) {
  if (!root) return 0
  return 1 + Math.max(height(root.left), height(root.right))
}

// Binary Search Tree lookup — O(h) where h = height
// Balanced BST: h = log n → O(log n)
// Skewed BST: h = n → O(n)
function bstSearch(root, target) {
  if (!root) return null
  if (root.val === target) return root
  if (target < root.val) return bstSearch(root.left, target)
  return bstSearch(root.right, target)
}

// Level-order traversal (BFS) — O(n) time, O(n) space for the queue
function levelOrder(root) {
  if (!root) return []
  const result = [], queue = [root]
  while (queue.length) {
    const level = []
    const size = queue.length
    for (let i = 0; i < size; i++) {
      const node = queue.shift()
      level.push(node.val)
      if (node.left)  queue.push(node.left)
      if (node.right) queue.push(node.right)
    }
    result.push(level)
  }
  return result
}

// Generate all subsets of an array
function subsets(nums) {
  const result = [[]]

  for (const num of nums) {           // n iterations
    const newSubsets = result.map(   // result grows: 1, 2, 4, ..., 2^(n-1) subsets
      subset => [...subset, num]
    )
    result.push(...newSubsets)
  }

  return result
}

// Analysis:
// After processing element i, result has 2^i subsets
// Total work = 2^0 + 2^1 + ... + 2^(n-1) = 2^n - 1
// Each subset copy costs O(n) in the worst case
// Total time: O(n × 2^n)
// Total space: O(n × 2^n) — must store all subsets

console.log(subsets([1, 2, 3]))
// [[], [1], [2], [1,2], [3], [1,3], [2,3], [1,2,3]] — 2^3 = 8 subsets