function sumArray(arr) {
  let total = 0;          // 1 operation
  for (let i = 0; i < arr.length; i++) {
    total += arr[i];      // n operations (runs once per element)
  }
  return total;           // 1 operation
}
// Exact count: n + 2 operations
// Big-O: O(n) — we drop the constant 2 because it becomes negligible for large n

// O(n) — loop body runs n times
function printAll(arr) {
  for (let i = 0; i < arr.length; i++) {
    console.log(arr[i]);   // O(1) work per iteration
  }
}

// Still O(n) — loop runs n/2 times, but O(n/2) = O(n)
function printEvery(arr) {
  for (let i = 0; i < arr.length; i += 2) {
    console.log(arr[i]);
  }
}

// O(log n) — problem halves each iteration
function logLoop(n) {
  for (let i = 1; i < n; i *= 2) {
    console.log(i);   // runs log₂(n) times total
  }
}

// O(n²) — outer runs n times, inner runs n times for each outer iteration
function printPairs(arr) {
  for (let i = 0; i < arr.length; i++) {       // n iterations
    for (let j = 0; j < arr.length; j++) {     // n iterations
      console.log(arr[i], arr[j]);             // n * n = n² total
    }
  }
}

// Still O(n²) — triangular pattern is n*(n-1)/2, but still quadratic
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]);
    }
  }
}

// O(n log n) — outer runs n times, inner runs log n times
function nLogN(arr) {
  for (let i = 0; i < arr.length; i++) {       // n iterations
    for (let j = 1; j < arr.length; j *= 2) { // log n iterations
      console.log(arr[i], j);
    }
  }
}

// O(n) — n recursive calls, O(1) work each
function factorial(n) {
  if (n <= 1) return 1;
  return n * factorial(n - 1);
  // Call chain: factorial(5) -> factorial(4) -> ... -> factorial(1)
  // Depth = n, work per call = O(1), total = O(n)
}

// O(2^n) — binary tree of calls, each node does O(1) work
function fibNaive(n) {
  if (n <= 1) return n;
  return fibNaive(n - 1) + fibNaive(n - 2);
  // Each call spawns 2 more. Tree has ~2^n nodes total.
}

// O(n log n) — recurrence T(n) = 2T(n/2) + 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 work
  // log n levels of recursion, n total work per level = O(n log n)
}

// Sequential: O(n) + O(n²) = O(n²)  — dominated by the quadratic term
function sequential(arr) {
  for (let x of arr) console.log(x);           // O(n)
  for (let i = 0; i < arr.length; i++)         // O(n²)
    for (let j = 0; j < arr.length; j++)
      console.log(i, j);
}

// Different inputs: O(a·b), NOT O(n²)
function cartesian(arrA, arrB) {
  for (let a of arrA)        // |arrA| = a
    for (let b of arrB)      // |arrB| = b
      console.log(a, b);     // total work = a * b
}

// Naive — O(2^n) time, O(n) space (only the call stack)
function fibSlow(n) {
  if (n <= 1) return n;
  return fibSlow(n - 1) + fibSlow(n - 2);
}

// Memoized — O(n) time, O(n) space (cache stores n results)
function fibFast(n, memo = new Map()) {
  if (n <= 1) return n;
  if (memo.has(n)) return memo.get(n);
  const result = fibFast(n - 1, memo) + fibFast(n - 2, memo);
  memo.set(n, result);
  return result;
}
// Trade-off: O(n) extra space to cut time from O(2^n) down to O(n)

// Problem 1 — what is the time complexity?
function mystery(n) {
  let count = 0;
  for (let i = n; i > 0; i = Math.floor(i / 3)) {
    count++;
  }
  return count;
}
// Answer: O(log₃ n) = O(log n). i divides by 3 each step.

// Problem 2 — what is the time and space complexity?
function twoSum(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 [];
}
// Answer: O(n) time (one pass through the array),
//         O(n) space (hash map stores up to n entries)

// Problem 3 — what is the time complexity?
function hasDuplicate(arr) {
  const seen = new Set();
  for (const num of arr) {
    if (seen.has(num)) return true;
    seen.add(num);
  }
  return false;
}
// Answer: O(n) time. Hash set lookup and insert are O(1) average.