Skip to main content

Documentation Index

Fetch the complete documentation index at: https://docs.matterai.so/llms.txt

Use this file to discover all available pages before exploring further.

Algorithm efficiency is critical for application performance. Inefficient algorithms can lead to excessive CPU usage, memory consumption, and poor user experience, especially when dealing with large datasets or frequent operations.Common algorithmic inefficiencies include:
  • Using algorithms with inappropriate time complexity for the problem
  • Implementing algorithms inefficiently
  • Not considering space-time tradeoffs
  • Redundant computations
  • Inappropriate data structure selection
This guide covers common anti-patterns related to algorithm selection and implementation, along with best practices for optimizing algorithmic performance.
// Anti-pattern: Bubble sort with O(n²) complexity
function bubbleSort(arr) {
  const n = arr.length;
  
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        // Swap elements
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
      }
    }
  }
  
  return arr;
}

// Better approach: Using built-in sort with O(n log n) complexity
function efficientSort(arr) {
  return [...arr].sort((a, b) => a - b);
}

// For custom sorting needs
function quickSort(arr) {
  if (arr.length <= 1) {
    return arr;
  }
  
  const pivot = arr[Math.floor(arr.length / 2)];
  const left = arr.filter(x => x < pivot);
  const middle = arr.filter(x => x === pivot);
  const right = arr.filter(x => x > pivot);
  
  return [...quickSort(left), ...middle, ...quickSort(right)];
}

// Anti-pattern: Selection sort with O(n²) complexity
public void selectionSort(int[] arr) {
    int n = arr.length;
    
    for (int i = 0; i < n - 1; i++) {
        int minIdx = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIdx]) {
                minIdx = j;
            }
        }
        
        // Swap elements
        int temp = arr[minIdx];
        arr[minIdx] = arr[i];
        arr[i] = temp;
    }
}

// Better approach: Using built-in sorting
public void efficientSort(int[] arr) {
    // Java's Arrays.sort uses a dual-pivot Quicksort
    Arrays.sort(arr);
}

// For objects or custom comparisons
public void sortObjects(List<Person> people) {
    Collections.sort(people, Comparator.comparing(Person::getAge));
}
Using inefficient sorting algorithms like bubble sort, selection sort, or insertion sort can lead to significant performance issues when dealing with large datasets.To optimize sorting operations:
  • Use built-in sorting functions which typically implement efficient algorithms
  • Choose algorithms based on data characteristics (nearly sorted, many duplicates, etc.)
  • Consider time and space complexity requirements
  • For small arrays, simple algorithms may actually be faster due to lower overhead
  • Use specialized algorithms for specific use cases (e.g., counting sort for integers in a known range)
  • Consider parallel sorting for very large datasets
  • Avoid unnecessary sorting operations
// Anti-pattern: Nested loops to find pairs with O(n²) complexity
function findPairsWithSum(arr, targetSum) {
  const pairs = [];
  
  for (let i = 0; i < arr.length; i++) {
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[i] + arr[j] === targetSum) {
        pairs.push([arr[i], arr[j]]);
      }
    }
  }
  
  return pairs;
}

// Better approach: Using a hash map with O(n) complexity
function findPairsWithSumEfficient(arr, targetSum) {
  const pairs = [];
  const seen = new Set();
  
  for (const num of arr) {
    const complement = targetSum - num;
    
    if (seen.has(complement)) {
      pairs.push([complement, num]);
    }
    
    seen.add(num);
  }
  
  return pairs;
}

# Anti-pattern: Nested loops to find pairs with O(n²) complexity
def find_pairs_with_sum(arr, target_sum):
    pairs = []
    
    for i in range(len(arr)):
        for j in range(i + 1, len(arr)):
            if arr[i] + arr[j] == target_sum:
                pairs.append([arr[i], arr[j]])
                
    return pairs

# Better approach: Using a hash set with O(n) complexity
def find_pairs_with_sum_efficient(arr, target_sum):
    pairs = []
    seen = set()
    
    for num in arr:
        complement = target_sum - num
        
        if complement in seen:
            pairs.append([complement, num])
            
        seen.add(num)
            
    return pairs
Using nested loops to find pairs or combinations in arrays leads to quadratic time complexity, which becomes problematic with large datasets.To optimize pair-finding operations:
  • Use hash-based data structures to reduce time complexity
  • Consider space-time tradeoffs (using more memory to reduce time)
  • For sorted arrays, consider using two-pointer techniques
  • Break early when possible
  • Consider using specialized algorithms for specific problems
  • Preprocess data when the same collection will be queried multiple times
  • Use appropriate data structures for the specific operation
// Anti-pattern: Linear search in sorted array with O(n) complexity
function linearSearch(sortedArr, target) {
  for (let i = 0; i < sortedArr.length; i++) {
    if (sortedArr[i] === target) {
      return i;
    }
    
    // Even with this optimization, still O(n) worst case
    if (sortedArr[i] > target) {
      return -1;
    }
  }
  
  return -1;
}

// Better approach: Binary search with O(log n) complexity
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;
    }
    
    if (sortedArr[mid] < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }
  
  return -1;
}

// Anti-pattern: Linear search in sorted array
public int linearSearch(int[] sortedArr, int target) {
    for (int i = 0; i < sortedArr.length; i++) {
        if (sortedArr[i] == target) {
            return i;
        }
        
        if (sortedArr[i] > target) {
            return -1;
        }
    }
    
    return -1;
}

// Better approach: Binary search
public int binarySearch(int[] sortedArr, int target) {
    int left = 0;
    int right = sortedArr.length - 1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2; // Avoids overflow
        
        if (sortedArr[mid] == target) {
            return mid;
        }
        
        if (sortedArr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    return -1;
}

// Even better: Using built-in binary search
public int builtInBinarySearch(int[] sortedArr, int target) {
    int index = Arrays.binarySearch(sortedArr, target);
    return index >= 0 ? index : -1;
}
Using linear search in sorted data structures fails to take advantage of the ordering, resulting in O(n) complexity instead of the possible O(log n).To optimize search operations in sorted data:
  • Use binary search instead of linear search
  • Consider using built-in binary search functions
  • For frequent searches, consider using tree-based data structures (BST, AVL, Red-Black)
  • For static datasets with frequent lookups, consider hash-based structures
  • Use interpolation search for uniformly distributed data
  • Consider exponential search for unbounded arrays
  • Use binary search variants for specific cases (e.g., finding insertion point)
// Anti-pattern: String concatenation in a loop
public String buildReport(List<String> items) {
    String report = "";
    for (String item : items) {
        // Creates a new String object in each iteration
        report = report + item + ", ";
    }
    return report;
}

// Better approach: Using StringBuilder
public String buildReportEfficiently(List<String> items) {
    StringBuilder reportBuilder = new StringBuilder();
    for (String item : items) {
        reportBuilder.append(item).append(", ");
    }
    return reportBuilder.toString();
}

// Anti-pattern: String concatenation in a loop
function buildReport(items) {
  let report = '';
  for (let i = 0; i < items.length; i++) {
    report = report + items[i] + ', ';
  }
  return report;
}

// Better approach: Using array join
function buildReportEfficiently(items) {
  return items.join(', ');
}
String concatenation in loops can lead to quadratic time complexity in some languages due to the immutable nature of strings, resulting in repeated memory allocations and copies.To optimize string concatenation:
  • Use string builders or buffers (StringBuilder in Java, StringBuffer for thread safety)
  • In JavaScript, use array.join() for simple concatenation
  • In Python, use ”.join(list) instead of += in loops
  • Consider using string interpolation for simple cases
  • Pre-allocate capacity when the final size is known or can be estimated
  • Minimize the number of concatenation operations
  • Consider using specialized libraries for very large string manipulations
// Anti-pattern: Redundant calculations
function calculateFactorials(n) {
  const results = [];
  
  for (let i = 1; i <= n; i++) {
    // Calculate factorial from scratch each time
    let factorial = 1;
    for (let j = 2; j <= i; j++) {
      factorial *= j;
    }
    results.push(factorial);
  }
  
  return results;
}

// Better approach: Using previous results
function calculateFactorialsEfficiently(n) {
  const results = [1]; // 0! = 1
  
  for (let i = 1; i <= n; i++) {
    // Use previous result
    results.push(results[i - 1] * i);
  }
  
  return results;
}

# Anti-pattern: Redundant calculations in Fibonacci
def fibonacci(n):
    if n <= 1:
        return n
    return fibonacci(n - 1) + fibonacci(n - 2)

# Better approach: Using memoization
def fibonacci_memoized(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fibonacci_memoized(n - 1, memo) + fibonacci_memoized(n - 2, memo)
    return memo[n]

# Even better: Using iteration
def fibonacci_iterative(n):
    if n <= 1:
        return n
    a, b = 0, 1
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b
Redundant recalculations occur when the same computation is performed multiple times unnecessarily, wasting CPU resources.To avoid redundant calculations:
  • Use memoization to cache results of expensive function calls
  • Implement dynamic programming approaches
  • Store and reuse intermediate results
  • Use iterative approaches instead of recursive ones when possible
  • Move invariant calculations outside of loops
  • Use lazy evaluation when appropriate
  • Consider using specialized libraries for common mathematical operations
// Anti-pattern: Inefficient traversal of linked list
class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

function findNodeAtIndex(head, index) {
  // O(n) operation for each access
  let current = head;
  let count = 0;
  
  while (current && count < index) {
    current = current.next;
    count++;
  }
  
  return current;
}

// Usage that causes inefficiency
function processLinkedListInefficiently(head, size) {
  for (let i = 0; i < size; i++) {
    // O(n) operation in each iteration, resulting in O(n²) complexity
    const node = findNodeAtIndex(head, i);
    processNode(node);
  }
}

// Better approach: Single traversal
function processLinkedListEfficiently(head) {
  let current = head;
  
  while (current) {
    processNode(current);
    current = current.next;
  }
}

// Anti-pattern: Inefficient traversal of nested data structures
public void processNestedListsInefficiently(List<List<Integer>> nestedLists) {
    int outerSize = nestedLists.size();
    
    // Repeatedly getting the size of inner lists
    for (int i = 0; i < outerSize; i++) {
        List<Integer> innerList = nestedLists.get(i);
        
        // This calls size() in each iteration
        for (int j = 0; j < innerList.size(); j++) {
            processValue(innerList.get(j));
        }
    }
}

// Better approach: Caching sizes and using enhanced for loops
public void processNestedListsEfficiently(List<List<Integer>> nestedLists) {
    // Enhanced for loop avoids explicit indexing
    for (List<Integer> innerList : nestedLists) {
        // Cache the size
        int innerSize = innerList.size();
        
        // Option 1: Traditional for loop with cached size
        for (int j = 0; j < innerSize; j++) {
            processValue(innerList.get(j));
        }
        
        // Option 2: Enhanced for loop (even better for most cases)
        for (Integer value : innerList) {
            processValue(value);
        }
    }
}
Inefficient data structure traversal can lead to unnecessary operations and poor performance, especially when dealing with linked structures or nested collections.To optimize data structure traversal:
  • Choose the appropriate traversal method for the data structure
  • Use iterators or enhanced for loops when possible
  • Cache collection sizes outside of loops
  • Avoid repeated lookups or traversals
  • Consider the access patterns of your data structure (sequential vs. random)
  • Use appropriate data structures for your access patterns
  • Consider using specialized traversal algorithms for specific structures
  • Be aware of the time complexity of traversal operations
// Anti-pattern: Poor hash function leading to collisions
public class BadHashExample {
    private int id;
    private String name;
    
    public BadHashExample(int id, String name) {
        this.id = id;
        this.name = name;
    }
    
    // Poor hash function that only uses part of the object state
    @Override
    public int hashCode() {
        return id % 10; // Only uses last digit of id, causing many collisions
    }
    
    @Override
    public boolean equals(Object obj) {
        if (this == obj) return true;
        if (obj == null || getClass() != obj.getClass()) return false;
        BadHashExample other = (BadHashExample) obj;
        return id == other.id && Objects.equals(name, other.name);
    }
}

// Better approach: Proper hash function
public class GoodHashExample {
    private int id;
    private String name;
    
    public GoodHashExample(int id, String name) {
        this.id = id;
        this.name = name;
    }
    
    // Better hash function using all fields and better distribution
    @Override
    public int hashCode() {
        return Objects.hash(id, name);
    }
    
    @Override
    public boolean equals(Object obj) {
        if (this == obj) return true;
        if (obj == null || getClass() != obj.getClass()) return false;
        GoodHashExample other = (GoodHashExample) obj;
        return id == other.id && Objects.equals(name, other.name);
    }
}

// Anti-pattern: Using non-primitive objects as keys without proper hashing
function processUserData(users) {
  const userDataMap = {};
  
  for (const user of users) {
    // Using objects as keys without proper string conversion
    // JavaScript will convert these to '[object Object]'
    userDataMap[user] = calculateUserMetrics(user);
  }
  
  // This will likely not work as expected
  return userDataMap[someUser];
}

// Better approach: Using proper keys or Map object
function processUserDataEfficiently(users) {
  // Option 1: Using a unique identifier as key
  const userDataMap = {};
  
  for (const user of users) {
    userDataMap[user.id] = calculateUserMetrics(user);
  }
  
  return userDataMap[someUser.id];
  
  // Option 2: Using Map object which allows object keys
  const userMap = new Map();
  
  for (const user of users) {
    userMap.set(user, calculateUserMetrics(user));
  }
  
  return userMap.get(someUser);
}
Excessive hash collisions can significantly degrade the performance of hash-based data structures like HashMaps, HashSets, and Dictionaries, turning O(1) operations into O(n) in worst cases.To minimize hash collisions:
  • Implement proper hashCode() methods that use all relevant fields
  • Ensure hash codes are well-distributed across the possible range
  • Follow the contract: if two objects are equal, they must have the same hash code
  • Use built-in hashing functions when available (Objects.hash in Java, etc.)
  • Consider the load factor of hash-based collections
  • Use appropriate initial capacity to minimize rehashing
  • In JavaScript, prefer Map over object literals for complex keys
  • Consider using specialized hash functions for specific use cases
  • Be cautious when using mutable objects as keys in hash-based collections
// Anti-pattern: Inefficient regular expression with catastrophic backtracking
function validateEmail(email) {
  // This regex can cause catastrophic backtracking on certain inputs
  const emailRegex = /^([a-zA-Z0-9]+([\.-]?[a-zA-Z0-9]+)*)*@([a-zA-Z0-9]+([\.-]?[a-zA-Z0-9]+)*)*\.[a-zA-Z]{2,}$/;
  
  return emailRegex.test(email);
}

// Better approach: More efficient regex without nested quantifiers
function validateEmailEfficiently(email) {
  // Simpler regex without nested quantifiers
  const emailRegex = /^[a-zA-Z0-9._%+-]+@[a-zA-Z0-9.-]+\.[a-zA-Z]{2,}$/;
  
  return emailRegex.test(email);
}

// Even better: Breaking down the validation
function validateEmailWithPrecheck(email) {
  // Quick pre-check to avoid regex for obvious non-emails
  if (!email || email.length < 5 || !email.includes('@') || !email.includes('.')) {
    return false;
  }
  
  // Now use regex for the complex part
  const emailRegex = /^[a-zA-Z0-9._%+-]+@[a-zA-Z0-9.-]+\.[a-zA-Z]{2,}$/;
  return emailRegex.test(email);
}

// Anti-pattern: Recompiling regular expressions in loops
public List<String> findEmailsInefficiently(List<String> texts) {
    List<String> emails = new ArrayList<>();
    
    for (String text : texts) {
        // Regex is recompiled in each iteration
        Matcher matcher = Pattern.compile("[a-zA-Z0-9._%+-]+@[a-zA-Z0-9.-]+\\.[a-zA-Z]{2,}").matcher(text);
        
        while (matcher.find()) {
            emails.add(matcher.group());
        }
    }
    
    return emails;
}

// Better approach: Compile regex once
public List<String> findEmailsEfficiently(List<String> texts) {
    List<String> emails = new ArrayList<>();
    
    // Compile regex once
    Pattern emailPattern = Pattern.compile("[a-zA-Z0-9._%+-]+@[a-zA-Z0-9.-]+\\.[a-zA-Z]{2,}");
    
    for (String text : texts) {
        Matcher matcher = emailPattern.matcher(text);
        
        while (matcher.find()) {
            emails.add(matcher.group());
        }
    }
    
    return emails;
}
Inefficient regular expressions can lead to performance issues, including catastrophic backtracking, excessive memory usage, and high CPU consumption.To optimize regular expression usage:
  • Avoid nested quantifiers (e.g., (a+)+) which can cause catastrophic backtracking
  • Compile regular expressions once, outside of loops
  • Use non-capturing groups (?:) when capture groups aren’t needed
  • Use possessive quantifiers (a++) or atomic groups (?>…) when available
  • Implement pre-checks to avoid regex for obvious cases
  • Consider using specialized validation libraries for common formats
  • Test regex performance with large inputs and edge cases
  • Break complex patterns into simpler parts
  • Use appropriate regex flags (case insensitivity, multiline, etc.)
// Anti-pattern: N+1 query problem in ORM
public void displayOrdersInefficiently() {
    // First query: Get all orders
    List<Order> orders = orderRepository.findAll();
    
    for (Order order : orders) {
        // N additional queries: Get customer for each order
        Customer customer = customerRepository.findById(order.getCustomerId());
        System.out.println("Order #" + order.getId() + " by " + customer.getName());
    }
}

// Better approach: Using join fetch or eager loading
public void displayOrdersEfficiently() {
    // Single query with join fetch
    List<Order> ordersWithCustomers = orderRepository.findAllWithCustomers();
    
    for (Order order : ordersWithCustomers) {
        // Customer is already loaded, no additional query needed
        Customer customer = order.getCustomer();
        System.out.println("Order #" + order.getId() + " by " + customer.getName());
    }
}

// Anti-pattern: N+1 query problem in Node.js/MongoDB
async function getUsersWithPostsInefficiently() {
  // First query: Get all users
  const users = await User.find({});
  
  // For each user, fetch their posts separately
  for (const user of users) {
    // N additional queries
    user.posts = await Post.find({ userId: user._id });
  }
  
  return users;
}

// Better approach: Using aggregation or population
async function getUsersWithPostsEfficiently() {
  // Option 1: Using MongoDB aggregation
  const usersWithPosts = await User.aggregate([
    {
      $lookup: {
        from: 'posts',
        localField: '_id',
        foreignField: 'userId',
        as: 'posts'
      }
    }
  ]);
  
  return usersWithPosts;
  
  // Option 2: Using Mongoose population
  const users = await User.find({}).populate('posts');
  return users;
}
The N+1 query problem occurs when an application makes one query to fetch a list of N items, then makes N additional queries to fetch related data for each item, resulting in N+1 total queries.To avoid the N+1 query problem:
  • Use eager loading, join fetches, or includes in ORMs
  • Implement batch loading of related entities
  • Use GraphQL with DataLoader for efficient batching
  • Consider denormalization for frequently accessed data
  • Use database-specific features like MongoDB’s $lookup or SQL JOINs
  • Implement caching strategies for related entities
  • Monitor and analyze database query patterns
  • Use query optimization tools provided by your ORM or database
  • Consider using specialized libraries like Facebook’s DataLoader
Algorithm Selection Checklist:

1. Time Complexity Analysis
   - Identify the expected input size range
   - Analyze worst-case, average-case, and best-case scenarios
   - Consider the growth rate of the algorithm (O(1), O(log n), O(n), O(n log n), O(n²), etc.)
   - Determine if the algorithm will scale with your data requirements
   - Benchmark with realistic data volumes

2. Space Complexity Considerations
   - Analyze memory requirements
   - Consider space-time tradeoffs
   - Evaluate if memory usage grows with input size
   - Determine if the algorithm fits within memory constraints
   - Consider cache efficiency and locality

3. Data Structure Selection
   - Choose data structures that optimize for your most frequent operations
   - Consider the access patterns (random vs. sequential)
   - Evaluate insertion, deletion, and lookup requirements
   - Consider memory overhead of different data structures
   - Evaluate thread-safety requirements

4. Algorithm Characteristics
   - Consider stability requirements (for sorting algorithms)
   - Evaluate in-place vs. copy requirements
   - Consider parallelization potential
   - Evaluate numerical stability (for numerical algorithms)
   - Consider algorithm simplicity and maintainability

5. Problem-Specific Considerations
   - Identify special properties of your data (sorted, nearly sorted, etc.)
   - Consider domain-specific optimizations
   - Evaluate if approximation algorithms are acceptable
   - Consider incremental processing requirements
   - Evaluate online vs. offline processing needs
Selecting the appropriate algorithm for a specific problem is crucial for application performance. The wrong algorithm can lead to unnecessary resource consumption and poor user experience.Key selection criteria:
  • Time complexity: Choose algorithms with appropriate complexity for your data size
  • Space complexity: Consider memory constraints and usage patterns
  • Data characteristics: Leverage special properties of your data
  • Access patterns: Optimize for your most frequent operations
  • Simplicity: Balance performance with maintainability
  • Scalability: Consider future growth in data volume
  • Specialized algorithms: Use domain-specific algorithms when appropriate
  • Built-in functions: Leverage optimized library implementations when available
  • Benchmarking: Test with realistic data volumes and patterns