Divide & Conquer Mastery

Divide & Conquer Mastery – Conquering Complexity Through Decomposition

Imagine you're the Chief Systems Architect ⚡ at a quantum computing research facility where massive computational problems must be decomposed into identical subproblems that can be solved independently and then combined efficiently to achieve exponential performance improvements:

🚀 The Quantum Computation Challenge:

🔬 Scenario 1: Quantum State Analysis (Merge Sort Pattern)

Problem: Sort 1 billion quantum measurement results for pattern analysis
Naive approach: Bubble sort = O(n²) = 10¹⁸ operations = impossible
Divide & conquer insight: Split data recursively, sort pieces, merge efficiently
Master theorem: T(n) = 2T(n/2) + O(n) = O(n log n) = 30 billion operations
Result: Reduce 10¹⁸ operations to 3×10¹⁰ - trillion-fold improvement!

⚛️ Scenario 2: Particle Collision Detection (Closest Pair Pattern)

Problem: Find closest pair among 1 million particles in 3D space
Brute force: Check all pairs = O(n²) = 10¹² distance calculations
Divide & conquer strategy: Recursively partition space, solve subproblems, merge results
Geometric insight: Closest pair is either within partition or crosses boundary
Result: O(n log n) = 20 million calculations - 50,000× faster than brute force

🌌 Scenario 3: Matrix Quantum Operations (Strassen's Algorithm)

Problem: Multiply two 1000×1000 quantum state matrices
Standard algorithm: O(n³) = 10⁹ scalar multiplications
Strassen's divide & conquer: Split matrices, 7 recursive calls instead of 8
Mathematical breakthrough: T(n) = 7T(n/2) + O(n²) = O(n^2.807)
Result: Reduce 10⁹ operations to 160 million - 6× improvement for large matrices

💡 The Divide & Conquer Mastery Principle:Divide & Conquer represents the pinnacle of algorithmic elegance - systematically decomposing complex problems into identical smaller subproblems, solving them recursively, and combining solutions efficiently to achieve logarithmic performance improvements that transform intractable problems into highly efficient solutions.

The Theoretical Foundation

Divide & Conquer Paradigm

Three-Step Framework:

Divide: Break problem into smaller subproblems of same type
Conquer: Solve subproblems recursively (or directly if small enough)
Combine: Merge subproblem solutions to solve original problem

Master Theorem for Complexity Analysis: For recurrence relation T(n) = aT(n/b) + f(n):

Case 1: f(n) = O(n^c) where c < log_b(a) → T(n) = Θ(n^(log_b(a)))
Case 2: f(n) = Θ(n^c log^k n) where c = log_b(a) → T(n) = Θ(n^c log^(k+1) n)
Case 3: f(n) = Ω(n^c) where c > log_b(a) → T(n) = Θ(f(n))

Key Design Principles:

Subproblem Independence: Solutions don't depend on other subproblems
Balanced Partitioning: Divide problem into roughly equal parts
Efficient Combination: Merge step should be as efficient as possible
Base Case Optimization: Handle small problems directly for efficiency

Mathematical Complexity Framework

Common Divide & Conquer Patterns:

Binary Division: T(n) = 2T(n/2) + O(n) → O(n log n) (Merge Sort)
Unbalanced Division: T(n) = T(n-1) + O(n) → O(n²) (Quick Sort worst case)
Multiple Subproblems: T(n) = 7T(n/2) + O(n²) → O(n^2.807) (Strassen)
Geometric Division: T(n) = 2T(n/2) + O(n) → O(n log n) (Closest Pair)

1. Advanced Sorting - Merge Sort Excellence

The Stable Sorting Foundation

/**
 * Merge Sort - Classic Divide & Conquer Sorting Algorithm
 * Guarantees O(n log n) performance with stable sorting
 */

function mergeSort(arr, startIndex = 0) {
    console.log(`=== Merge Sort Analysis ===`);
    
    function mergeSortRecursive(arr, left, right, depth = 0) {
        const indent = '  '.repeat(depth);
        const size = right - left + 1;
        
        console.log(`${indent}Sorting range [${left}, ${right}], size=${size}: [${arr.slice(left, right + 1).join(', ')}]`);
        
        // Base case
        if (left >= right) {
            console.log(`${indent}Base case: single element or empty, returning`);
            return;
        }
        
        // Divide
        const mid = Math.floor((left + right) / 2);
        console.log(`${indent}Dividing at mid=${mid}:`);
        console.log(`${indent}  Left half: [${left}, ${mid}]`);
        console.log(`${indent}  Right half: [${mid + 1}, ${right}]`);
        
        // Conquer
        console.log(`${indent}Recursively sorting left half:`);
        mergeSortRecursive(arr, left, mid, depth + 1);
        
        console.log(`${indent}Recursively sorting right half:`);
        mergeSortRecursive(arr, mid + 1, right, depth + 1);
        
        // Combine
        console.log(`${indent}Merging sorted halves:`);
        console.log(`${indent}  Left: [${arr.slice(left, mid + 1).join(', ')}]`);
        console.log(`${indent}  Right: [${arr.slice(mid + 1, right + 1).join(', ')}]`);
        
        merge(arr, left, mid, right, depth);
        
        console.log(`${indent}Merged result: [${arr.slice(left, right + 1).join(', ')}]`);
    }
    
    function merge(arr, left, mid, right, depth) {
        const indent = '  '.repeat(depth);
        
        // Create temporary arrays
        const leftArr = arr.slice(left, mid + 1);
        const rightArr = arr.slice(mid + 1, right + 1);
        
        console.log(`${indent}Merging process:`);
        
        let i = 0, j = 0, k = left;
        
        // Merge the arrays
        while (i < leftArr.length && j < rightArr.length) {
            console.log(`${indent}  Comparing ${leftArr[i]} vs ${rightArr[j]}`);
            
            if (leftArr[i] <= rightArr[j]) {
                arr[k] = leftArr[i];
                console.log(`${indent}  ${leftArr[i]} ≤ ${rightArr[j]}, take ${leftArr[i]}`);
                i++;
            } else {
                arr[k] = rightArr[j];
                console.log(`${indent}  ${leftArr[i]} > ${rightArr[j]}, take ${rightArr[j]}`);
                j++;
            }
            k++;
        }
        
        // Copy remaining elements
        while (i < leftArr.length) {
            arr[k] = leftArr[i];
            console.log(`${indent}  Copying remaining left: ${leftArr[i]}`);
            i++;
            k++;
        }
        
        while (j < rightArr.length) {
            arr[k] = rightArr[j];
            console.log(`${indent}  Copying remaining right: ${rightArr[j]}`);
            j++;
            k++;
        }
    }
    
    const sortedArray = [...arr];
    console.log(`Original array: [${arr.join(', ')}]`);
    console.log(`Array size: ${arr.length}`);
    console.log(`Expected complexity: O(n log n) = O(${arr.length} × ${Math.ceil(Math.log2(arr.length))}) = ${arr.length * Math.ceil(Math.log2(arr.length))} operations\n`);
    
    const startTime = performance.now();
    mergeSortRecursive(sortedArray, 0, sortedArray.length - 1);
    const endTime = performance.now();
    
    console.log(`\nFinal sorted array: [${sortedArray.join(', ')}]`);
    console.log(`Time taken: ${(endTime - startTime).toFixed(2)}ms`);
    
    return sortedArray;
}

// Optimized merge sort with insertion sort for small arrays
function mergeSortOptimized(arr, threshold = 10) {
    console.log(`\n=== Optimized Merge Sort (threshold=${threshold}) ===`);
    
    function insertionSort(arr, left, right) {
        console.log(`  Using insertion sort for small range [${left}, ${right}]`);
        
        for (let i = left + 1; i <= right; i++) {
            const key = arr[i];
            let j = i - 1;
            
            while (j >= left && arr[j] > key) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = key;
        }
    }
    
    function mergeSortHybrid(arr, left, right, depth = 0) {
        const size = right - left + 1;
        
        if (size <= threshold) {
            insertionSort(arr, left, right);
            return;
        }
        
        const mid = Math.floor((left + right) / 2);
        
        mergeSortHybrid(arr, left, mid, depth + 1);
        mergeSortHybrid(arr, mid + 1, right, depth + 1);
        
        // Only merge if necessary (arrays might already be sorted)
        if (arr[mid] <= arr[mid + 1]) {
            console.log(`  Skip merge - already sorted at depth ${depth}`);
            return;
        }
        
        merge(arr, left, mid, right);
    }
    
    function merge(arr, left, mid, right) {
        const leftArr = arr.slice(left, mid + 1);
        const rightArr = arr.slice(mid + 1, right + 1);
        
        let i = 0, j = 0, k = left;
        
        while (i < leftArr.length && j < rightArr.length) {
            arr[k++] = leftArr[i] <= rightArr[j] ? leftArr[i++] : rightArr[j++];
        }
        
        while (i < leftArr.length) arr[k++] = leftArr[i++];
        while (j < rightArr.length) arr[k++] = rightArr[j++];
    }
    
    const optimizedArray = [...arr];
    console.log(`Optimizing for arrays with threshold ${threshold}`);
    
    const startTime = performance.now();
    mergeSortHybrid(optimizedArray, 0, optimizedArray.length - 1);
    const endTime = performance.now();
    
    console.log(`Optimized result: [${optimizedArray.join(', ')}]`);
    console.log(`Time taken: ${(endTime - startTime).toFixed(2)}ms`);
    
    return optimizedArray;
}

// Run examples
console.log("=== Merge Sort Examples ===");

const unsortedArray = [64, 34, 25, 12, 22, 11, 90, 88, 76, 50, 42];
mergeSort(unsortedArray);
mergeSortOptimized(unsortedArray);

2. Quick Sort - Partitioning Excellence

The In-Place Sorting Master

/**
 * Quick Sort - Divide & Conquer with In-Place Partitioning
 * Average O(n log n), worst case O(n²), space O(log n)
 */

function quickSort(arr) {
    console.log(`=== Quick Sort Analysis ===`);
    
    function partition(arr, low, high, depth) {
        const indent = '  '.repeat(depth);
        console.log(`${indent}Partitioning range [${low}, ${high}]: [${arr.slice(low, high + 1).join(', ')}]`);
        
        const pivot = arr[high];  // Choose last element as pivot
        console.log(`${indent}Pivot: ${pivot} (at index ${high})`);
        
        let i = low - 1;  // Index of smaller element
        
        console.log(`${indent}Partitioning process:`);
        
        for (let j = low; j < high; j++) {
            console.log(`${indent}  Comparing ${arr[j]} with pivot ${pivot}:`);
            
            if (arr[j] <= pivot) {
                i++;
                if (i !== j) {
                    [arr[i], arr[j]] = [arr[j], arr[i]];
                    console.log(`${indent}    ${arr[j]} ≤ ${pivot}, swap ${arr[j]} with ${arr[i]} at positions ${j}, ${i}`);
                } else {
                    console.log(`${indent}    ${arr[j]} ≤ ${pivot}, already in correct position`);
                }
                console.log(`${indent}    Array now: [${arr.slice(low, high + 1).join(', ')}]`);
            } else {
                console.log(`${indent}    ${arr[j]} > ${pivot}, no swap needed`);
            }
        }
        
        // Place pivot in correct position
        i++;
        [arr[i], arr[high]] = [arr[high], arr[i]];
        console.log(`${indent}Placing pivot ${pivot} at final position ${i}`);
        console.log(`${indent}Final partition: [${arr.slice(low, high + 1).join(', ')}]`);
        console.log(`${indent}Left partition: [${arr.slice(low, i).join(', ')}] (all ≤ ${pivot})`);
        console.log(`${indent}Right partition: [${arr.slice(i + 1, high + 1).join(', ')}] (all > ${pivot})`);
        
        return i;
    }
    
    function quickSortRecursive(arr, low, high, depth = 0) {
        const indent = '  '.repeat(depth);
        const size = high - low + 1;
        
        console.log(`${indent}Sorting range [${low}, ${high}], size=${size}: [${arr.slice(low, high + 1).join(', ')}]`);
        
        if (low < high) {
            // Partition the array
            const pivotIndex = partition(arr, low, high, depth);
            
            console.log(`${indent}Pivot ${arr[pivotIndex]} is now at correct position ${pivotIndex}`);
            
            // Recursively sort elements before and after partition
            console.log(`${indent}Recursively sorting left subarray:`);
            quickSortRecursive(arr, low, pivotIndex - 1, depth + 1);
            
            console.log(`${indent}Recursively sorting right subarray:`);
            quickSortRecursive(arr, pivotIndex + 1, high, depth + 1);
        } else {
            console.log(`${indent}Base case: single element or empty, no sorting needed`);
        }
    }
    
    const sortedArray = [...arr];
    console.log(`Original array: [${arr.join(', ')}]`);
    console.log(`Array size: ${arr.length}`);
    console.log(`Average complexity: O(n log n), Worst case: O(n²)\n`);
    
    const startTime = performance.now();
    quickSortRecursive(sortedArray, 0, sortedArray.length - 1);
    const endTime = performance.now();
    
    console.log(`\nFinal sorted array: [${sortedArray.join(', ')}]`);
    console.log(`Time taken: ${(endTime - startTime).toFixed(2)}ms`);
    
    return sortedArray;
}

// Quick Sort with random pivot (to avoid worst case)
function quickSortRandomized(arr) {
    console.log(`\n=== Randomized Quick Sort ===`);
    
    function randomPartition(arr, low, high) {
        // Randomly choose pivot and swap with last element
        const randomIndex = Math.floor(Math.random() * (high - low + 1)) + low;
        [arr[randomIndex], arr[high]] = [arr[high], arr[randomIndex]];
        
        console.log(`Random pivot: ${arr[high]} (originally at index ${randomIndex})`);
        
        return partition(arr, low, high);
    }
    
    function partition(arr, low, high) {
        const pivot = arr[high];
        let i = low - 1;
        
        for (let j = low; j < high; j++) {
            if (arr[j] <= pivot) {
                i++;
                [arr[i], arr[j]] = [arr[j], arr[i]];
            }
        }
        
        [arr[i + 1], arr[high]] = [arr[high], arr[i + 1]];
        return i + 1;
    }
    
    function quickSortRandom(arr, low, high, depth = 0) {
        const indent = '  '.repeat(depth);
        
        if (low < high) {
            console.log(`${indent}Sorting [${low}, ${high}]: [${arr.slice(low, high + 1).join(', ')}]`);
            
            const pivotIndex = randomPartition(arr, low, high);
            
            console.log(`${indent}After partition: [${arr.slice(low, high + 1).join(', ')}]`);
            console.log(`${indent}Pivot ${arr[pivotIndex]} at position ${pivotIndex}`);
            
            quickSortRandom(arr, low, pivotIndex - 1, depth + 1);
            quickSortRandom(arr, pivotIndex + 1, high, depth + 1);
        }
    }
    
    const randomizedArray = [...arr];
    
    const startTime = performance.now();
    quickSortRandom(randomizedArray, 0, randomizedArray.length - 1);
    const endTime = performance.now();
    
    console.log(`Randomized result: [${randomizedArray.join(', ')}]`);
    console.log(`Time taken: ${(endTime - startTime).toFixed(2)}ms`);
    
    return randomizedArray;
}

// Three-way partitioning for arrays with many duplicates
function quickSort3Way(arr) {
    console.log(`\n=== 3-Way Quick Sort (for duplicates) ===`);
    
    function partition3Way(arr, low, high) {
        const pivot = arr[low];
        let lt = low;      // arr[low..lt-1] < pivot
        let gt = high;     // arr[gt+1..high] > pivot
        let i = low + 1;   // arr[lt..i-1] == pivot
        
        console.log(`3-way partitioning around pivot ${pivot}:`);
        
        while (i <= gt) {
            if (arr[i] < pivot) {
                [arr[lt], arr[i]] = [arr[i], arr[lt]];
                lt++;
                i++;
                console.log(`  ${arr[i-1]} < ${pivot}: move to left partition`);
            } else if (arr[i] > pivot) {
                [arr[i], arr[gt]] = [arr[gt], arr[i]];
                gt--;
                console.log(`  ${arr[gt+1]} > ${pivot}: move to right partition`);
            } else {
                i++;
                console.log(`  ${arr[i-1]} == ${pivot}: keep in middle`);
            }
            
            console.log(`    Current: [${arr.slice(low, high + 1).join(', ')}]`);
            console.log(`    < pivot: [${low}, ${lt-1}], == pivot: [${lt}, ${gt}], > pivot: [${gt+1}, ${high}]`);
        }
        
        return { lt, gt };
    }
    
    function quickSort3WayRecursive(arr, low, high, depth = 0) {
        const indent = '  '.repeat(depth);
        
        if (low >= high) return;
        
        console.log(`${indent}3-way sorting [${low}, ${high}]: [${arr.slice(low, high + 1).join(', ')}]`);
        
        const { lt, gt } = partition3Way(arr, low, high);
        
        console.log(`${indent}After 3-way partition:`);
        console.log(`${indent}  < pivot: [${arr.slice(low, lt).join(', ')}]`);
        console.log(`${indent}  == pivot: [${arr.slice(lt, gt + 1).join(', ')}]`);
        console.log(`${indent}  > pivot: [${arr.slice(gt + 1, high + 1).join(', ')}]`);
        
        quickSort3WayRecursive(arr, low, lt - 1, depth + 1);
        quickSort3WayRecursive(arr, gt + 1, high, depth + 1);
    }
    
    const threeWayArray = [...arr];
    
    const startTime = performance.now();
    quickSort3WayRecursive(threeWayArray, 0, threeWayArray.length - 1);
    const endTime = performance.now();
    
    console.log(`3-way result: [${threeWayArray.join(', ')}]`);
    console.log(`Time taken: ${(endTime - startTime).toFixed(2)}ms`);
    
    return threeWayArray;
}

// Run examples
console.log("=== Quick Sort Examples ===");

const unsortedArray = [64, 34, 25, 12, 22, 11, 90, 34, 22, 50];  // With duplicates
quickSort(unsortedArray);
quickSortRandomized(unsortedArray);
quickSort3Way(unsortedArray);

3. Closest Pair Problem - Geometric Divide & Conquer

The Spatial Optimization Challenge

/**
 * Closest Pair of Points using Divide & Conquer
 * Geometric problem solving with O(n log n) complexity
 */

function closestPair(points) {
    console.log(`=== Closest Pair Problem ===`);
    console.log(`Finding closest pair among ${points.length} points`);
    
    // Display points
    console.log("Points:");
    points.forEach((point, i) => {
        console.log(`P${i}: (${point.x}, ${point.y})`);
    });
    
    function distance(p1, p2) {
        return Math.sqrt((p1.x - p2.x) ** 2 + (p1.y - p2.y) ** 2);
    }
    
    function bruteForce(points) {
        console.log(`  Brute force for ${points.length} points`);
        
        let minDist = Infinity;
        let closestPair = null;
        
        for (let i = 0; i < points.length; i++) {
            for (let j = i + 1; j < points.length; j++) {
                const dist = distance(points[i], points[j]);
                console.log(`    Distance P${i}(${points[i].x},${points[i].y}) to P${j}(${points[j].x},${points[j].y}): ${dist.toFixed(2)}`);
                
                if (dist < minDist) {
                    minDist = dist;
                    closestPair = [points[i], points[j]];
                    console.log(`      New minimum: ${dist.toFixed(2)}`);
                }
            }
        }
        
        return { distance: minDist, pair: closestPair };
    }
    
    function closestPairRec(px, py, depth = 0) {
        const indent = '  '.repeat(depth);
        const n = px.length;
        
        console.log(`${indent}Divide & Conquer: ${n} points`);
        console.log(`${indent}Points by X: [${px.map(p => `(${p.x},${p.y})`).join(', ')}]`);
        
        // Base case: use brute force for small sets
        if (n <= 3) {
            console.log(`${indent}Base case: ${n} points, using brute force`);
            return bruteForce(px);
        }
        
        // Divide
        const mid = Math.floor(n / 2);
        const midPoint = px[mid];
        
        console.log(`${indent}Dividing at x = ${midPoint.x}`);
        
        const pyl = py.filter(point => point.x <= midPoint.x);
        const pyr = py.filter(point => point.x > midPoint.x);
        
        console.log(`${indent}Left: ${pyl.length} points, Right: ${pyr.length} points`);
        
        // Conquer
        console.log(`${indent}Solving left half:`);
        const leftResult = closestPairRec(px.slice(0, mid), pyl, depth + 1);
        
        console.log(`${indent}Solving right half:`);
        const rightResult = closestPairRec(px.slice(mid), pyr, depth + 1);
        
        // Find minimum of the two halves
        let minResult = leftResult.distance < rightResult.distance ? leftResult : rightResult;
        
        console.log(`${indent}Left minimum: ${leftResult.distance.toFixed(2)}`);
        console.log(`${indent}Right minimum: ${rightResult.distance.toFixed(2)}`);
        console.log(`${indent}Overall minimum so far: ${minResult.distance.toFixed(2)}`);
        
        // Combine: check points near the dividing line
        const strip = py.filter(point => Math.abs(point.x - midPoint.x) < minResult.distance);
        
        console.log(`${indent}Checking strip of width ${(2 * minResult.distance).toFixed(2)} around x = ${midPoint.x}`);
        console.log(`${indent}Strip contains ${strip.length} points`);
        
        if (strip.length > 1) {
            console.log(`${indent}Checking strip points:`);
            
            for (let i = 0; i < strip.length; i++) {
                for (let j = i + 1; j < strip.length && (strip[j].y - strip[i].y) < minResult.distance; j++) {
                    const dist = distance(strip[i], strip[j]);
                    
                    console.log(`${indent}  Strip pair (${strip[i].x},${strip[i].y}) to (${strip[j].x},${strip[j].y}): ${dist.toFixed(2)}`);
                    
                    if (dist < minResult.distance) {
                        minResult = { distance: dist, pair: [strip[i], strip[j]] };
                        console.log(`${indent}    New global minimum: ${dist.toFixed(2)}`);
                    }
                }
            }
        }
        
        console.log(`${indent}Minimum for this subproblem: ${minResult.distance.toFixed(2)}`);
        return minResult;
    }
    
    // Sort points by x and y coordinates
    const px = [...points].sort((a, b) => a.x - b.x);
    const py = [...points].sort((a, b) => a.y - b.y);
    
    console.log("\nSorted by X:");
    px.forEach((point, i) => console.log(`  ${i}: (${point.x}, ${point.y})`));
    
    console.log("\nSorted by Y:");
    py.forEach((point, i) => console.log(`  ${i}: (${point.x}, ${point.y})`));
    
    console.log("\nStarting divide & conquer algorithm:");
    
    const startTime = performance.now();
    const result = closestPairRec(px, py);
    const endTime = performance.now();
    
    console.log(`\n=== Closest Pair Results ===`);
    console.log(`Closest distance: ${result.distance.toFixed(2)}`);
    console.log(`Closest pair: (${result.pair[0].x}, ${result.pair[0].y}) and (${result.pair[1].x}, ${result.pair[1].y})`);
    console.log(`Time taken: ${(endTime - startTime).toFixed(2)}ms`);
    
    // Verify with brute force for comparison
    console.log("\nVerification with brute force:");
    const bruteForceResult = bruteForce(points);
    console.log(`Brute force result: ${bruteForceResult.distance.toFixed(2)}`);
    console.log(`Results match: ${Math.abs(result.distance - bruteForceResult.distance) < 0.001}`);
    
    return result;
}

// Run examples
console.log("=== Closest Pair Examples ===");

const testPoints = [
    { x: 2, y: 3 },
    { x: 12, y: 30 },
    { x: 40, y: 50 },
    { x: 5, y: 1 },
    { x: 12, y: 10 },
    { x: 3, y: 4 },
    { x: 8, y: 6 },
    { x: 15, y: 20 }
];

closestPair(testPoints);

4. Strassen's Matrix Multiplication - Mathematical Innovation

The Computational Algebra Breakthrough

/**
 * Strassen's Matrix Multiplication Algorithm
 * Reduces complexity from O(n³) to O(n^2.807) using divide & conquer
 */

function strassenMultiplication(A, B) {
    console.log(`=== Strassen's Matrix Multiplication ===`);
    
    function printMatrix(matrix, name) {
        console.log(`${name}:`);
        matrix.forEach((row, i) => {
            console.log(`  [${row.map(val => val.toString().padStart(4)).join('')}]`);
        });
    }
    
    function addMatrix(A, B) {
        const n = A.length;
        const result = Array.from({ length: n }, () => Array(n).fill(0));
        
        for (let i = 0; i < n; i++) {
            for (let j = 0; j < n; j++) {
                result[i][j] = A[i][j] + B[i][j];
            }
        }
        
        return result;
    }
    
    function subtractMatrix(A, B) {
        const n = A.length;
        const result = Array.from({ length: n }, () => Array(n).fill(0));
        
        for (let i = 0; i < n; i++) {
            for (let j = 0; j < n; j++) {
                result[i][j] = A[i][j] - B[i][j];
            }
        }
        
        return result;
    }
    
    function standardMultiply(A, B) {
        const n = A.length;
        const result = Array.from({ length: n }, () => Array(n).fill(0));
        
        console.log(`    Standard multiplication for ${n}×${n} matrices`);
        
        for (let i = 0; i < n; i++) {
            for (let j = 0; j < n; j++) {
                for (let k = 0; k < n; k++) {
                    result[i][j] += A[i][k] * B[k][j];
                }
            }
        }
        
        return result;
    }
    
    function strassenRecursive(A, B, depth = 0) {
        const indent = '  '.repeat(depth);
        const n = A.length;
        
        console.log(`${indent}Strassen multiply: ${n}×${n} matrices`);
        
        // Base case: use standard multiplication for small matrices
        if (n <= 2) {
            console.log(`${indent}Base case: ${n}×${n}, using standard multiplication`);
            return standardMultiply(A, B);
        }
        
        // Divide matrices into quadrants
        const mid = Math.floor(n / 2);
        
        console.log(`${indent}Dividing ${n}×${n} matrices into ${mid}×${mid} quadrants`);
        
        // Extract quadrants
        const A11 = A.slice(0, mid).map(row => row.slice(0, mid));
        const A12 = A.slice(0, mid).map(row => row.slice(mid));
        const A21 = A.slice(mid).map(row => row.slice(0, mid));
        const A22 = A.slice(mid).map(row => row.slice(mid));
        
        const B11 = B.slice(0, mid).map(row => row.slice(0, mid));
        const B12 = B.slice(0, mid).map(row => row.slice(mid));
        const B21 = B.slice(mid).map(row => row.slice(0, mid));
        const B22 = B.slice(mid).map(row => row.slice(mid));
        
        console.log(`${indent}Computing 7 Strassen products (instead of 8 standard products):`);
        
        // Compute the 7 products (Strassen's key insight)
        console.log(`${indent}P1 = A11 × (B12 - B22)`);
        const P1 = strassenRecursive(A11, subtractMatrix(B12, B22), depth + 1);
        
        console.log(`${indent}P2 = (A11 + A12) × B22`);
        const P2 = strassenRecursive(addMatrix(A11, A12), B22, depth + 1);
        
        console.log(`${indent}P3 = (A21 + A22) × B11`);
        const P3 = strassenRecursive(addMatrix(A21, A22), B11, depth + 1);
        
        console.log(`${indent}P4 = A22 × (B21 - B11)`);
        const P4 = strassenRecursive(A22, subtractMatrix(B21, B11), depth + 1);
        
        console.log(`${indent}P5 = (A11 + A22) × (B11 + B22)`);
        const P5 = strassenRecursive(addMatrix(A11, A22), addMatrix(B11, B22), depth + 1);
        
        console.log(`${indent}P6 = (A12 - A22) × (B21 + B22)`);
        const P6 = strassenRecursive(subtractMatrix(A12, A22), addMatrix(B21, B22), depth + 1);
        
        console.log(`${indent}P7 = (A11 - A21) × (B11 + B12)`);
        const P7 = strassenRecursive(subtractMatrix(A11, A21), addMatrix(B11, B12), depth + 1);
        
        // Combine results
        console.log(`${indent}Combining results using Strassen's formulas:`);
        
        console.log(`${indent}C11 = P5 + P4 - P2 + P6`);
        const C11 = addMatrix(subtractMatrix(addMatrix(P5, P4), P2), P6);
        
        console.log(`${indent}C12 = P1 + P2`);
        const C12 = addMatrix(P1, P2);
        
        console.log(`${indent}C21 = P3 + P4`);
        const C21 = addMatrix(P3, P4);
        
        console.log(`${indent}C22 = P5 + P1 - P3 - P7`);
        const C22 = subtractMatrix(subtractMatrix(addMatrix(P5, P1), P3), P7);
        
        // Combine quadrants into result matrix
        const result = Array.from({ length: n }, () => Array(n).fill(0));
        
        for (let i = 0; i < mid; i++) {
            for (let j = 0; j < mid; j++) {
                result[i][j] = C11[i][j];
                result[i][j + mid] = C12[i][j];
                result[i + mid][j] = C21[i][j];
                result[i + mid][j + mid] = C22[i][j];
            }
        }
        
        console.log(`${indent}Combined ${n}×${n} result matrix`);
        
        return result;
    }
    
    const n = A.length;
    
    console.log(`Matrix size: ${n}×${n}`);
    console.log(`Standard complexity: O(n³) = O(${n}³) = ${n * n * n} operations`);
    console.log(`Strassen complexity: O(n^2.807) ≈ ${Math.floor(Math.pow(n, 2.807))} operations`);
    console.log(`Theoretical speedup: ${(n * n * n / Math.pow(n, 2.807)).toFixed(2)}×\n`);
    
    printMatrix(A, "Matrix A");
    printMatrix(B, "Matrix B");
    
    console.log("\nStarting Strassen's algorithm:");
    
    const startTime = performance.now();
    const result = strassenRecursive(A, B);
    const endTime = performance.now();
    
    console.log("\n=== Strassen Results ===");
    printMatrix(result, "Result C = A × B");
    console.log(`Time taken: ${(endTime - startTime).toFixed(2)}ms`);
    
    // Verify with standard multiplication
    console.log("\nVerification with standard multiplication:");
    const standardResult = standardMultiply(A, B);
    let matches = true;
    
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < n; j++) {
            if (result[i][j] !== standardResult[i][j]) {
                matches = false;
                break;
            }
        }
        if (!matches) break;
    }
    
    console.log(`Results match: ${matches}`);
    
    return result;
}

// Run examples
console.log("=== Strassen Matrix Multiplication Examples ===");

const matrixA = [
    [1, 2, 3, 4],
    [5, 6, 7, 8],
    [9, 10, 11, 12],
    [13, 14, 15, 16]
];

const matrixB = [
    [17, 18, 19, 20],
    [21, 22, 23, 24],
    [25, 26, 27, 28],
    [29, 30, 31, 32]
];

strassenMultiplication(matrixA, matrixB);

Summary

Divide & Conquer Mastery Achieved

Algorithmic Decomposition Excellence:

Merge Sort: Stable O(n log n) sorting with guaranteed performance and optimal comparison complexity
Quick Sort: In-place partitioning with average O(n log n) and advanced optimization techniques
Closest Pair: Geometric problem solving with O(n log n) spatial divide and conquer
Strassen's Algorithm: Mathematical innovation reducing matrix multiplication complexity

Algorithm Design Principles:

Divide & Conquer Framework:

Problem Decomposition: Break complex problems into identical smaller subproblems
Recursive Solution: Apply same algorithm to subproblems until base case reached
Efficient Combination: Merge subproblem solutions with minimal overhead
Complexity Analysis: Apply Master Theorem for mathematical performance guarantees

Optimization Strategies:

Base Case Optimization: Use efficient algorithms for small problem sizes
Randomization: Avoid worst-case scenarios through random choices
Hybrid Approaches: Combine multiple algorithms for optimal performance
Memory Optimization: In-place algorithms and efficient data structures

Real-World Applications Mastery

Large-Scale Computing:

Big Data Processing: Distributed sorting and searching across massive datasets
Scientific Computing: Matrix operations for simulations and numerical analysis
Computer Graphics: Geometric algorithms for rendering and collision detection
Database Systems: Query optimization and index construction

High-Performance Systems:

Parallel Processing: Natural decomposition for multi-core and distributed systems
Memory Hierarchy: Cache-efficient algorithms through spatial and temporal locality
Real-Time Systems: Predictable performance through guaranteed complexity bounds
Embedded Systems: Efficient algorithms for resource-constrained environments

Machine Learning & AI:

Neural Networks: Matrix operations for forward and backward propagation
Computer Vision: Image processing and feature detection algorithms
Natural Language Processing: Text analysis and pattern matching at scale
Recommendation Systems: Similarity computation across large user bases

Mathematical and Theoretical Foundations

Master Theorem Applications:

T(n) = 2T(n/2) + O(n): Merge Sort, Closest Pair → O(n log n)
T(n) = T(n-1) + O(n): Quick Sort worst case → O(n²)
T(n) = 7T(n/2) + O(n²): Strassen's Algorithm → O(n^2.807)
T(n) = 2T(n/2) + O(1): Binary Search → O(log n)

Complexity Analysis:

Time Complexity: Logarithmic improvements through balanced decomposition
Space Complexity: Trade-offs between in-place and auxiliary space algorithms
Stability: Preservation of relative order in sorting algorithms
Optimality: Lower bounds and asymptotically optimal algorithms

Advanced Techniques:

Randomization: Expected performance improvements and worst-case avoidance
Parallelization: Natural parallelism in independent subproblems
Cache Optimization: Memory access patterns for modern computer architectures
Numerical Stability: Error propagation in recursive mathematical computations

Strategic Problem-Solving Framework

Divide & Conquer Design Process:

1. Problem Analysis:
   - Identify if problem has recursive substructure
   - Determine how to divide into subproblems
   - Design efficient combination strategy
   
2. Algorithm Design:
   - Choose appropriate base case size
   - Implement recursive decomposition
   - Optimize combination phase
   
3. Performance Optimization:
   - Apply Master Theorem for complexity analysis
   - Consider hybrid approaches for small cases
   - Implement cache-efficient memory access
   
4. Practical Implementation:
   - Handle edge cases and boundary conditions
   - Add randomization if needed
   - Consider parallel processing opportunities

Problem Recognition Patterns:

Sorting/Searching: Natural candidates for logarithmic improvements
Geometric Problems: Spatial decomposition for computational geometry
Matrix Operations: Block-based algorithms for numerical computations
Tree/Graph Problems: Recursive structure enables divide and conquer

You now possess mastery of divide and conquer algorithms that enables logarithmic performance improvements through systematic problem decomposition. This expertise provides the algorithmic foundation for high-performance computing systems that must process massive datasets efficiently while maintaining mathematical optimality guarantees.

The progression from basic recursion to sophisticated mathematical algorithms represents fundamental computational thinking - the ability to recognize recursive problem structure and apply systematic decomposition to achieve optimal asymptotic performance through elegant mathematical insights.

This divide and conquer mastery is essential for building scalable systems that must handle exponentially growing data while maintaining predictable performance and leveraging modern parallel computing architectures effectively.