Algorithm Optimization

Understanding Time Complexity (Big O)

Time complexity describes how the runtime of an algorithm grows as the input size increases. Understanding Big O notation is crucial for writing performant code.

Common Time Complexities

// O(1) - Constant time
function getFirst(arr) {
  return arr[0]; // Always takes same time
}

// O(log n) - Logarithmic time
function binarySearch(arr, target) {
  let left = 0, right = arr.length - 1;
  
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    
    if (arr[mid] === target) return mid;
    if (arr[mid] < target) left = mid + 1;
    else right = mid - 1;
  }
  
  return -1;
}

// O(n) - Linear time
function findMax(arr) {
  let max = arr[0];
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] > max) max = arr[i];
  }
  return max;
}

// O(n log n) - Linearithmic time
function quickSort(arr) {
  if (arr.length <= 1) return arr;
  
  const pivot = arr[arr.length - 1];
  const left = arr.filter((x, i) => x <= pivot && i < arr.length - 1);
  const right = arr.filter(x => x > pivot);
  
  return [...quickSort(left), pivot, ...quickSort(right)];
}

// O(n²) - Quadratic time
function bubbleSort(arr) {
  for (let i = 0; i < arr.length; i++) {
    for (let j = 0; j < arr.length - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
      }
    }
  }
  return arr;
}

// O(2ⁿ) - Exponential time
function fibonacci(n) {
  if (n <= 1) return n;
  return fibonacci(n - 1) + fibonacci(n - 2); // Very slow!
}

Optimizing Array Operations

// ❌ Bad: O(n²) - nested loops
function findDuplicates(arr) {
  const duplicates = [];
  for (let i = 0; i < arr.length; i++) {
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[i] === arr[j] && !duplicates.includes(arr[i])) {
        duplicates.push(arr[i]);
      }
    }
  }
  return duplicates;
}

// ✅ Good: O(n) - using Set
function findDuplicatesOptimized(arr) {
  const seen = new Set();
  const duplicates = new Set();
  
  for (const item of arr) {
    if (seen.has(item)) {
      duplicates.add(item);
    }
    seen.add(item);
  }
  
  return Array.from(duplicates);
}

// ❌ Bad: O(n) for each lookup
function frequentLookups(arr, queries) {
  return queries.map(query => arr.includes(query));
}

// ✅ Good: O(1) for each lookup using Set
function frequentLookupsOptimized(arr, queries) {
  const set = new Set(arr);
  return queries.map(query => set.has(query));
}

Data Structure Selection

// Array vs Set vs Map - Choose wisely
// Array: Good for ordered data, iteration, index access
// Set: Good for uniqueness, membership tests O(1)
// Map: Good for key-value pairs, frequent lookups O(1)

// ❌ Bad: Using array for frequent lookups
const users = [
  { id: 1, name: 'Alice' },
  { id: 2, name: 'Bob' }
];

function getUserById(id) {
  return users.find(u => u.id === id); // O(n)
}

// ✅ Good: Using Map for O(1) lookups
const usersMap = new Map([
  [1, { id: 1, name: 'Alice' }],
  [2, { id: 2, name: 'Bob' }]
]);

function getUserByIdOptimized(id) {
  return usersMap.get(id); // O(1)
}

// Converting between structures
const arrayToMap = arr => new Map(arr.map(item => [item.id, item]));
const setToArray = set => Array.from(set);
const mapToObject = map => Object.fromEntries(map);

String Operations Optimization

// ❌ Bad: String concatenation in loop (O(n²))
function buildString(arr) {
  let result = '';
  for (let i = 0; i < arr.length; i++) {
    result += arr[i]; // Creates new string each iteration
  }
  return result;
}

// ✅ Good: Use array join (O(n))
function buildStringOptimized(arr) {
  return arr.join('');
}

// ✅ Good: Use template literals for clarity
function buildHTML(items) {
  return items.map(item => `
    

      
${item.title}
      
${item.description}
    
  `).join('');
}

// ❌ Bad: Multiple string operations
function processText(text) {
  text = text.trim();
  text = text.toLowerCase();
  text = text.replace(/\s+/g, ' ');
  return text;
}

// ✅ Good: Chain operations
function processTextOptimized(text) {
  return text.trim().toLowerCase().replace(/\s+/g, ' ');
}

Efficient Sorting

// Built-in sort is O(n log n)
// Custom sort with proper comparator
const numbers = [5, 2, 8, 1, 9];

// ❌ Bad: String comparison for numbers
numbers.sort(); // ['1', '2', '5', '8', '9'] - wrong order

// ✅ Good: Numeric comparison
numbers.sort((a, b) => a - b); // [1, 2, 5, 8, 9]

// Sorting objects efficiently
const users = [
  { name: 'Alice', age: 30 },
  { name: 'Bob', age: 25 },
  { name: 'Charlie', age: 35 }
];

// ✅ Sort by multiple criteria
users.sort((a, b) => {
  // First by age
  if (a.age !== b.age) {
    return a.age - b.age;
  }
  // Then by name
  return a.name.localeCompare(b.name);
});

// For already sorted data, use binary insert
function binaryInsert(arr, item) {
  let left = 0;
  let right = arr.length;
  
  while (left < right) {
    const mid = Math.floor((left + right) / 2);
    if (arr[mid] < item) {
      left = mid + 1;
    } else {
      right = mid;
    }
  }
  
  arr.splice(left, 0, item);
  return arr;
}

Loop Optimization

// ❌ Bad: Inefficient loop patterns
for (let i = 0; i < arr.length; i++) {
  // Recalculates length each iteration
}

// ✅ Good: Cache length
const len = arr.length;
for (let i = 0; i < len; i++) {
  // Uses cached value
}

// ✅ Even better: Use for...of for readability
for (const item of arr) {
  // Modern, clean, fast
}

// ❌ Bad: Nested loops on same array
for (let i = 0; i < arr.length; i++) {
  for (let j = 0; j < arr.length; j++) {
    if (i !== j && arr[i] === arr[j]) {
      // O(n²)
    }
  }
}

// ✅ Good: Single pass with Map
const seen = new Map();
for (const item of arr) {
  seen.set(item, (seen.get(item) || 0) + 1);
}

// Break early when possible
function findFirst(arr, predicate) {
  for (const item of arr) {
    if (predicate(item)) {
      return item; // Stop as soon as found
    }
  }
  return null;
}

Recursive Optimization

// ❌ Bad: Recursive without memoization
function fibonacci(n) {
  if (n <= 1) return n;
  return fibonacci(n - 1) + fibonacci(n - 2);
}

// ✅ Good: With memoization
function fibonacciMemo(n, memo = {}) {
  if (n <= 1) return n;
  if (memo[n]) return memo[n];
  
  memo[n] = fibonacciMemo(n - 1, memo) + fibonacciMemo(n - 2, memo);
  return memo[n];
}

// ✅ Better: Iterative approach
function fibonacciIterative(n) {
  if (n <= 1) return n;
  
  let prev = 0, curr = 1;
  
  for (let i = 2; i <= n; i++) {
    [prev, curr] = [curr, prev + curr];
  }
  
  return curr;
}

// Tail recursion (optimize with trampoline)
function factorial(n, acc = 1) {
  if (n <= 1) return acc;
  return factorial(n - 1, n * acc);
}

Object Property Access

// ❌ Bad: Repeated property access
function calculate(obj) {
  const result = obj.data.values.items.length * 
                 obj.data.values.multiplier +
                 obj.data.values.offset;
  return result;
}

// ✅ Good: Destructure once
function calculateOptimized(obj) {
  const { length, multiplier, offset } = obj.data.values.items;
  return length * multiplier + offset;
}

// Use hasOwnProperty for safe property checks
if (obj.hasOwnProperty('prop')) {
  // Better than: if (obj.prop !== undefined)
}