Description
Algorithm decision matrix: Big-O bounds, real-world constants, 3 data regimes, three recommendations.
Do not pick the first algorithm that comes to mind. Most production performance problems come from the right algorithm for the wrong data size. This framework forces data-regime consideration. STEP 1 — CANDIDATES List 3+ algorithmic approaches. Each: core idea (1 sentence), best/avg/worst time complexity, space complexity, comparison/hash/structure based. Example for sorting: QuickSort (O(n log n), O(log n), not stable), MergeSort (O(n log n), O(n), stable), TimSort (O(n log n), O(n), stable, adaptive O(n) on nearly-sorted). STEP 2 — REAL-WORLD CONSTANTS - Cache locality: array-based 10-100× faster than pointer-chasing on modern CPUs. - Branch misprediction: unpredictable branches (random pivot) can be 2-3× slower. - Parallelizability: MapReduce-friendly algorithms win on large data. - Input distribution: some degrade gracefully (timsort), others have pathological cases (quicksort on sorted data). STEP 3 — 3×N DECISION MATRIX Rows = data regimes (Small N≤100, Medium N≤10⁵, Large N≥10⁶). Columns = candidates. Cell = expected ms. | Regime | Candidate A | Candidate B | Candidate C | |--------|------------|------------|------------| | Small | 0.2ms | 0.3ms | 0.1ms | | Medium | 15ms | 22ms | 18ms | | Large | 1.2s | 3.4s | 0.9s | STEP 4 — THREE RECOMMENDATIONS A. BEST GENERAL: performs across all regimes with acceptable worst-case. B. MEMORY-CONSTRAINED: survives with O(1) extra space. C. SIX-MONTH REGRET: data grows 100×—which choice do you regret? Pick the scalable one. STEP 5 — WORKED EXAMPLE: Apply to concrete input N=50, show intermediate states. OUTPUT: Comparison table, 3×N matrix, three recommendations, worked trace.
No comments yet. Be the first!