Lesson 15-Algorithm Testing and Optimization Practice

Why Testing Algorithms Matters

Let’s start with a fundamental question: why should you test your algorithms? Isn’t it enough that the code “looks right”?

No. Here’s why:

1. Algorithms have edge cases: An algorithm might work for n = 10 but fail for n = 0, n = 1, or n = 10000.
2. Algorithms can have subtle bugs: Off-by-one errors, integer overflow, incorrect handling of negative numbers—these are easy to miss in code review.
3. Algorithms need to perform: An algorithm might be correct but slow. You need to measure performance, not just correctness.
4. Algorithms evolve: As you optimize or modify an algorithm, you need tests to ensure you haven’t broken anything.

The High Cost of Algorithm Bugs

Let me share a real-world story. In 1996, the European Space Agency’s Ariane 5 rocket exploded just 40 seconds after launch. The cause? An algorithm tried to convert a 64-bit floating-point number to a 16-bit integer, causing an overflow. The rocket’s navigation system failed, and the self-destruct mechanism activated.

Cost: $370 million.

In frontend development, the costs are rarely that dramatic—but they can still be significant:

• A sorting algorithm that crashes on empty arrays can break your entire app
• A debounce function that doesn’t properly clear timers can cause memory leaks
• A virtual DOM diffing algorithm with edge cases can cause UI glitches that frustrate users

flowchart TD
    A[Write Algorithm] --> B{Test It?}
    B -->|No| C[Ship to Production]
    C --> D{Edge Case Occurs?}
    D -->|Yes| E[User Experiences Bug]
    E --> F[Bad Reviews / Lost Revenue]
    D -->|No| G[You Got Lucky]
    B -->|Yes| H[Write Unit Tests]
    H --> I[Property-Based Testing]
    I --> J[Performance Benchmarking]
    J --> K[Load Testing]
    K --> L[Ship with Confidence]
    L --> M[Happy Users / Maintainable Code]
    
    style E fill:#ff6b6b
    style F fill:#ff6b6b
    style M fill:#51cf66
    style L fill:#51cf66

A Real Example: Binary Search

Here’s a binary search implementation with a subtle bug:

// Binary search with a bug!
function binarySearchBad(arr, target) {
  let left = 0;
  let right = arr.length - 1;
  
  while (left <= right) {
    const mid = Math.floor((left + right) / 2); // BUG: can overflow for large arrays!
    
    if (arr[mid] === target) return mid;
    if (arr[mid] < target) left = mid + 1;
    else right = mid - 1;
  }
  
  return -1;
}

// Binary search with a bug!
function binarySearchBad(arr, target) {
  let left = 0;
  let right = arr.length - 1;
  
  while (left <= right) {
    const mid = Math.floor((left + right) / 2); // BUG: can overflow for large arrays!
    
    if (arr[mid] === target) return mid;
    if (arr[mid] < target) left = mid + 1;
    else right = mid - 1;
  }
  
  return -1;
}

The bug: left + right can exceed the maximum integer size (2^31 – 1 in JavaScript, though BigInt makes this less of a concern). A correct implementation:

// Binary search (correct)
function binarySearch(arr, target) {
  let left = 0;
  let right = arr.length - 1;
  
  while (left <= right) {
    const mid = left + Math.floor((right - left) / 2); // Safe from overflow!
    
    if (arr[mid] === target) return mid;
    if (arr[mid] < target) left = mid + 1;
    else right = mid - 1;
  }
  
  return -1;
}

// Binary search (correct)
function binarySearch(arr, target) {
  let left = 0;
  let right = arr.length - 1;
  
  while (left <= right) {
    const mid = left + Math.floor((right - left) / 2); // Safe from overflow!
    
    if (arr[mid] === target) return mid;
    if (arr[mid] < target) left = mid + 1;
    else right = mid - 1;
  }
  
  return -1;
}

This is the kind of bug that testing catches. If you only test with small arrays, you’ll miss it.