Optimizing Time Complexity

const sizes = [10, 100, 1000];
const algorithms = [
  { name: 'O(1)', func: () => 1 },
  { name: 'O(log n)', func: (n) => Math.log2(n) },
  { name: 'O(n)', func: (n) => n },
  { name: 'O(n log n)', func: (n) => n * Math.log2(n) },
  { name: 'O(n²)', func: (n) => n * n }
];

sizes.forEach(size => {
  console.log(`\nInput size: ${size}`);
  algorithms.forEach(alg => {
    console.log(`${alg.name}: ${alg.func(size).toFixed(2)} steps`);
  });
});

const fib = memoize((n) => {
  if (n <= 1) return n;
  return fib(n - 1) + fib(n - 2);
});

function fibonacciTabulation(n) {
  if (n <= 1) return n;
  
  let dp = new Array(n + 1);
  dp[0] = 0;
  dp[1] = 1;
  
  for (let i = 2; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
  }
  
  return dp[n];
}

console.log(fibonacciTabulation(6)); // Output: 8

const hashTable = new Map();
hashTable.set("name", "Alice");
hashTable.set("age", 30);

console.log(hashTable.get("name")); // Alice
hashTable.delete("age");

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

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

    if (arr[mid] === target) {
      return mid;
    } else if (arr[mid] < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }

  return -1; // Not found
}

// Example usage:
const sortedArray = [1, 3, 5, 7, 9, 11, 13];
console.log(binarySearch(sortedArray, 7)); // Output: 3

function binarySearchRecursive(arr, target, left = 0, right = arr.length - 1) {
  if (left > right) return -1;

  let mid = Math.floor((left + right) / 2);

  if (arr[mid] === target) {
    return mid;
  } else if (arr[mid] < target) {
    return binarySearchRecursive(arr, target, mid + 1, right);
  } else {
    return binarySearchRecursive(arr, target, left, mid - 1);
  }
}

// Example usage:
const sortedArray = [2, 4, 6, 8, 10, 12];
console.log(binarySearchRecursive(sortedArray, 10)); // Output: 4

function twoSum(nums, target) {
  let left = 0;
  let right = nums.length - 1;

  while (left < right) {
    const sum = nums[left] + nums[right];
    if (sum === target) {
      return [left, right];
    } else if (sum < target) {
      left++;
    } else {
      right--;
    }
  }

  return [];
}

function isPalindrome(s) {
  let left = 0;
  let right = s.length - 1;

  while (left < right) {
    if (s[left] !== s[right]) {
      return false;
    }
    left++;
    right--;
  }

  return true;
}

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

function twoSumSorted(nums, target) {
  let left = 0;
  let right = nums.length - 1;

  while (left < right) {
    const sum = nums[left] + nums[right];
    if (sum === target) {
      return [left, right];
    } else if (sum < target) {
      left++;
    } else {
      right--;
    }
  }

  return [];
}

function mergeIntervals(intervals) {
  intervals.sort((a, b) => a[0] - b[0]);

  const merged = [];
  for (const interval of intervals) {
    if (merged.length === 0 || merged[merged.length - 1][1] < interval[0]) {
      merged.push(interval);
    } else {
      merged[merged.length - 1][1] = Math.max(merged[merged.length - 1][1], interval[1]);
    }
  }

  return merged;
}

const activities = [
  { name: 'A1', start: 0, end: 6 },
  { name: 'A2', start: 3, end: 4 },
  { name: 'A3', start: 1, end: 2 },
  { name: 'A4', start: 5, end: 7 },
  { name: 'A5', start: 8, end: 9 },
  { name: 'A6', start: 5, end: 9 }
];

function selectActivities(activities) {
  // Sort by finish time
  activities.sort((a, b) => a.end - b.end);
  const selected = [activities[0]];
  let lastEnd = activities[0].end;

  for (let i = 1; i < activities.length; i++) {
    if (activities[i].start >= lastEnd) {
      selected.push(activities[i]);
      lastEnd = activities[i].end;
    }
  }

  return selected;
}

console.log(selectActivities(activities));
// Output: [{ name: 'A3', start: 1, end: 2 }, { name: 'A2', start: 3, end: 4 }, { name: 'A4', start: 5, end: 7 }, { name: 'A5', start: 8, end: 9 }]

function isEven(num) {
  return (num & 1) === 0;
}

console.log(isEven(4)); // true
console.log(isEven(5)); // false

let a = 10;
let b = 20;

a = a ^ b; // a becomes 30 (10^20)
b = a ^ b; // b becomes 10 (30^20)
a = a ^ b; // a becomes 20 (30^10)

console.log(a); // 20
console.log(b); // 10

function findSingle(arr) {
  let result = 0;
  for (let i = 0; i < arr.length; i++) {
    result ^= arr[i];
  }
  return result;
}

console.log(findSingle([1, 2, 3, 2, 1])); // 3

class DynamicArray {
  constructor() {
    this.data = new Array(1);
    this.size = 0;
    this.capacity = 1;
  }

  push(value) {
    if (this.size === this.capacity) {
      // Resize: double the capacity
      const newCapacity = this.capacity * 2;
      const newData = new Array(newCapacity);
      for (let i = 0; i < this.size; i++) {
        newData[i] = this.data[i];
      }
      this.data = newData;
      this.capacity = newCapacity;
    }
    this.data[this.size] = value;
    this.size++;
  }

  // Amortized O(1) for push due to rare resizing
}

function sumArithmeticSequence(a1, an, n) {
  return n / 2 * (a1 + an);
}

// Example usage:
const sum = sumArithmeticSequence(1, 10, 10); // Returns 55

function fibonacciFormula(n) {
  const phi = (1 + Math.sqrt(5)) / 2;
  const psi = (1 - Math.sqrt(5)) / 2;
  return Math.round((Math.pow(phi, n) - Math.pow(psi, n)) / Math.sqrt(5));
}

// Example usage:
console.log(fibonacciFormula(10)); // Returns 55