// This loop runs 3n + 7 operations
function example(arr) {
  let count = 0
  for (let i = 0; i < arr.length; i++) {  // n iterations
    count += arr[i]   // 1 op
    count *= 2        // 1 op
    count -= 1        // 1 op
  }
  // 7 constant-time operations after the loop
  return count
}
// Running time: 3n + 7
// After dropping constants & lower-order terms: O(n)

// Two separate sections — pick the dominant term
function twoSections(arr, matrix) {
  let sum = 0
  for (const x of arr) sum += x         // O(n)

  for (const row of matrix)             // O(n²) — n×n matrix
    for (const cell of row)
      sum += cell

  return sum
  // Total: O(n) + O(n²) = O(n²)
}

// Array element access — always one operation
function getFirst(arr) {
  return arr[0]   // O(1) regardless of arr.length
}

// Hash map lookup — O(1) average case
function isPresent(map, key) {
  return map.has(key)
}

// Even many O(1) operations is still O(1)
function complexButConstant(n) {
  let a = n * 2     // O(1)
  let b = a + 100   // O(1)
  let c = b % 7     // O(1)
  return c
  // Total: O(4) → O(1) after dropping constants
}

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

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

    if (sortedArr[mid] === target) return mid
    else if (sortedArr[mid] < target) left = mid + 1  // discard left half
    else right = mid - 1                               // discard right half
  }

  return -1
}

// After each iteration, search space is halved:
// n=1000 → 500 → 250 → 125 → 62 → 31 → 15 → 7 → 3 → 1
// At most log₂(1000) ≈ 10 iterations for ANY sorted 1000-element array!

// Finding the maximum — must check every element
function findMax(arr) {
  let max = -Infinity
  for (const val of arr) {    // n iterations
    if (val > max) max = val  // O(1) work per step
  }
  return max
}

// Two separate loops → O(2n) = O(n)
function sumAndProduct(arr) {
  let sum = 0
  for (const x of arr) sum += x      // first O(n) pass

  let product = 1
  for (const x of arr) product *= x  // second O(n) pass

  return { sum, product }
  // Total: O(2n) = O(n)   ← NOT O(n²)
}

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

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

  return merge(left, right)  // O(n) merge step
}

// Recurrence: T(n) = 2·T(n/2) + O(n)
// Master Theorem → T(n) = O(n log n)
//
// Recursion tree visualization:
// Level 0: 1 subproblem of size n     → n work
// Level 1: 2 subproblems of size n/2  → n work total
// Level 2: 4 subproblems of size n/4  → n work total
// ...
// Level log₂n: n subproblems of size 1 → n work total
// Total: n × log₂n levels = O(n log n)

// Bubble sort — O(n²)
function bubbleSort(arr) {
  for (let i = 0; i < arr.length; i++) {        // n iterations
    for (let j = 0; j < arr.length - 1; j++) {  // n iterations
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]
      }
    }
  }
  return arr
}
// Total: n × n = n² comparisons → O(n²)

// All pairs — still O(n²) even with j = i + 1
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
  // Iterations: n(n-1)/2 ≈ n²/2 → O(n²)
}

// Naive Fibonacci — exponential due to recomputation
function fibSlow(n) {
  if (n <= 1) return n
  return fibSlow(n - 1) + fibSlow(n - 2)
  // Each call spawns 2 more → 2ⁿ total calls
}

// Generating all subsets — O(2ⁿ) unavoidable (there ARE 2ⁿ subsets)
function allSubsets(arr) {
  if (arr.length === 0) return [[]]
  const [first, ...rest] = arr
  const subsetsWithout = allSubsets(rest)
  const subsetsWith = subsetsWithout.map(s => [first, ...s])
  return [...subsetsWithout, ...subsetsWith]
  // n=3 → 8 subsets, n=20 → 1,048,576, n=40 → over 1 trillion
}

// Fix Fibonacci with memoization → O(n)
const memo = new Map()
function fibFast(n) {
  if (n <= 1) return n
  if (memo.has(n)) return memo.get(n)
  const result = fibFast(n - 1) + fibFast(n - 2)
  memo.set(n, result)
  return result
}

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), ...arr.slice(i + 1)]
    const perms     = permutations(remaining)   // recurse on n-1 elements
    for (const perm of perms) result.push([current, ...perm])
  }
  return result
}
// n=3 → 6 permutations
// n=5 → 120 permutations
// n=10 → 3,628,800 permutations
// n=15 → 1,307,674,368,000 permutations

// Approach 1: Brute force — O(n²) time, O(1) space
function twoSumBrute(nums, target) {
  for (let i = 0; i < nums.length; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      if (nums[i] + nums[j] === target) return [i, j]
    }
  }
  return []
}
// n=10,000 → ~50,000,000 iterations

// Approach 2: Hash map — O(n) time, O(n) space
function twoSumOptimal(nums, target) {
  const seen = new Map()
  for (let i = 0; i < nums.length; i++) {
    const complement = target - nums[i]
    if (seen.has(complement)) return [seen.get(complement), i]
    seen.set(nums[i], i)
  }
  return []
}
// n=10,000 → ~10,000 iterations
// Trade-off: O(n) extra space purchased O(n) speed improvement