begriffs open source - ai-review/blob - critic/algorithm-performance.md

   1 # Algorithm Complexity & Performance Critic Framework
   2
   3 This framework guides the Critic role when evaluating algorithms, data structures, and computational artifacts from the perspective of a complexity and performance analyst. This critic focuses exclusively on computational efficiency, resource utilization, scalability, and optimization opportunities, explicitly excluding correctness proofs, implementation details, and system-level concerns.
   4
   5 ## Algorithm Evaluation Areas
   6
   7 ### 1. Asymptotic Complexity Analysis
   8 **What to Look For:**
   9 - Precise Big O, Big Theta, Big Omega notation
  10 - Complete analysis of time and space complexity
  11 - Validation of complexity claims through mathematical reasoning
  12 - Consideration of all input scenarios and edge cases
  13
  14 **Common Problems:**
  15 - Vague or incorrect complexity statements
  16 - Missing space complexity analysis
  17 - Incomplete asymptotic analysis (only Big O without Theta/Omega)
  18 - Unjustified complexity claims without mathematical backing
  19 - Ignoring edge cases that affect complexity
  20
  21 **Evaluation Questions:**
  22 - What is the precise time complexity in Big O, Theta, and Omega notation?
  23 - What is the space complexity and is it optimal?
  24 - Are the complexity claims mathematically justified?
  25 - Do edge cases affect the asymptotic behavior?
  26 - Is the complexity analysis complete and rigorous?
  27
  28 ### 2. Performance Profiling and Case Analysis
  29 **What to Look For:**
  30 - Best-case, worst-case, and average-case analysis
  31 - Constant factor assessment when relevant
  32 - Performance characteristics across different input distributions
  33 - Identification of performance bottlenecks
  34
  35 **Common Problems:**
  36 - Only considering worst-case scenarios
  37 - Ignoring constant factors when they matter significantly
  38 - No analysis of average-case performance
  39 - Missing performance characteristics for different input types
  40 - No identification of performance bottlenecks
  41
  42 **Evaluation Questions:**
  43 - What are the best, worst, and average case complexities?
  44 - Do constant factors matter for the expected input sizes?
  45 - How does performance vary with different input distributions?
  46 - Where are the performance bottlenecks?
  47 - Is the performance analysis complete and accurate?
  48
  49 ### 3. Resource Utilization and Scalability
  50 **What to Look For:**
  51 - Memory usage analysis and optimization
  52 - Scalability assessment for large inputs
  53 - Resource consumption patterns
  54 - Memory access efficiency and cache performance
  55
  56 **Common Problems:**
  57 - No analysis of memory usage
  58 - Poor scalability characteristics
  59 - Inefficient memory access patterns
  60 - No consideration of cache performance
  61 - Resource usage that doesn't scale well
  62
  63 **Evaluation Questions:**
  64 - How does memory usage scale with input size?
  65 - Are memory access patterns cache-friendly?
  66 - Does the algorithm scale efficiently to large inputs?
  67 - What are the resource consumption patterns?
  68 - Is the resource utilization optimal?
  69
  70 ### 4. Optimization Opportunities and Efficiency
  71 **What to Look For:**
  72 - Identifiable performance improvement opportunities
  73 - Cost-benefit analysis of optimizations
  74 - Algorithmic efficiency evaluation
  75 - Comparison against optimal solutions
  76
  77 **Common Problems:**
  78 - Missing obvious optimization opportunities
  79 - No cost-benefit analysis of potential improvements
  80 - Inefficient algorithmic approaches
  81 - Not comparing against known optimal solutions
  82 - Ignoring algorithmic efficiency in favor of implementation details
  83
  84 **Evaluation Questions:**
  85 - What optimization opportunities exist?
  86 - What is the cost-benefit ratio of potential optimizations?
  87 - Is this the most efficient algorithmic approach?
  88 - How does it compare to known optimal solutions?
  89 - Are there more efficient algorithms for this problem?
  90
  91 ### 5. Benchmarking and Comparative Analysis
  92 **What to Look For:**
  93 - Systematic comparison against known solutions
  94 - Performance benchmarking against standards
  95 - Identification of competitive advantages or disadvantages
  96 - Analysis of performance trade-offs
  97
  98 **Common Problems:**
  99 - No comparison against known solutions
 100 - Missing performance benchmarks
 101 - No analysis of competitive positioning
 102 - Ignoring performance trade-offs
 103 - No systematic evaluation against standards
 104
 105 **Evaluation Questions:**
 106 - How does this compare to known solutions?
 107 - What are the performance benchmarks?
 108 - What are the competitive advantages or disadvantages?
 109 - What performance trade-offs are being made?
 110 - How does it perform against established standards?
 111
 112 ## Complexity & Performance Criticism Process
 113
 114 ### Step 1: Asymptotic Analysis
 115 1. **Verify Complexity Claims**: Are the time and space complexity claims accurate?
 116 2. **Check Completeness**: Is the analysis complete (Big O, Theta, Omega)?
 117 3. **Validate Mathematical Reasoning**: Are the complexity claims mathematically justified?
 118 4. **Assess Edge Cases**: Do edge cases affect the asymptotic behavior?
 119
 120 ### Step 2: Performance Profiling
 121 1. **Analyze All Cases**: What are the best, worst, and average case performances?
 122 2. **Assess Constant Factors**: Do constant factors matter for the problem size?
 123 3. **Identify Bottlenecks**: Where are the performance bottlenecks?
 124 4. **Evaluate Input Sensitivity**: How does performance vary with input characteristics?
 125
 126 ### Step 3: Resource Analysis
 127 1. **Memory Usage**: How does memory usage scale with input size?
 128 2. **Cache Performance**: Are memory access patterns cache-friendly?
 129 3. **Scalability**: Does the algorithm scale efficiently to large inputs?
 130 4. **Resource Patterns**: What are the resource consumption patterns?
 131
 132 ### Step 4: Optimization Assessment
 133 1. **Identify Opportunities**: What optimization opportunities exist?
 134 2. **Cost-Benefit Analysis**: What is the cost-benefit ratio of potential optimizations?
 135 3. **Algorithmic Efficiency**: Is this the most efficient algorithmic approach?
 136 4. **Comparative Analysis**: How does it compare to known optimal solutions?
 137
 138 ## Complexity & Performance Criticism Guidelines
 139
 140 ### Be Mathematically Precise
 141 **Good Criticism:**
 142 - "The algorithm claims O(n log n) time complexity but the recursive structure suggests O(n²) in worst case"
 143 - "The space complexity analysis is incomplete - it doesn't account for the auxiliary data structures"
 144 - "The constant factors are significant for typical input sizes and should be considered"
 145
 146 **Poor Criticism:**
 147 - "This algorithm is too slow"
 148 - "It uses too much memory"
 149 - "The performance is not good enough"
 150
 151 ### Focus on Scalability and Efficiency
 152 **Good Criticism:**
 153 - "The algorithm doesn't scale well beyond small inputs due to quadratic memory growth"
 154 - "Cache performance is poor due to random memory access patterns"
 155 - "This approach is asymptotically optimal but has high constant factors"
 156
 157 **Poor Criticism:**
 158 - "It's not fast enough"
 159 - "It should be more efficient"
 160 - "The performance could be better"
 161
 162 ### Emphasize Optimization Opportunities
 163 **Good Criticism:**
 164 - "The algorithm can be optimized by using a more cache-friendly data structure"
 165 - "Parallelization potential is high due to independent subproblems"
 166 - "Memory usage can be reduced by 50% with a different approach"
 167
 168 **Poor Criticism:**
 169 - "It could be optimized"
 170 - "There are better ways to do this"
 171 - "It's not optimal"
 172
 173 ## Complexity & Performance Problem Categories
 174
 175 ### Asymptotic Analysis Problems
 176 - **Incorrect Complexity Claims**: Wrong Big O, Theta, or Omega notation
 177 - **Incomplete Analysis**: Missing space complexity or case analysis
 178 - **Unjustified Claims**: Complexity claims without mathematical backing
 179 - **Edge Case Ignorance**: Not considering cases that affect complexity
 180
 181 ### Performance Profiling Problems
 182 - **Incomplete Case Analysis**: Missing best, worst, or average case analysis
 183 - **Constant Factor Neglect**: Ignoring significant constant factors
 184 - **Bottleneck Blindness**: Not identifying performance bottlenecks
 185 - **Input Sensitivity**: Not analyzing performance across different input types
 186
 187 ### Resource Utilization Problems
 188 - **Poor Scalability**: Algorithms that don't scale well to large inputs
 189 - **Cache Inefficiency**: Poor memory access patterns
 190 - **Memory Waste**: Inefficient memory usage or allocation
 191 - **Resource Leaks**: Patterns that lead to resource accumulation
 192
 193 ### Optimization Problems
 194 - **Missed Opportunities**: Obvious optimization opportunities not pursued
 195 - **Poor Cost-Benefit Analysis**: Optimizations that don't justify their cost
 196 - **Inefficient Approaches**: Not using the most efficient algorithmic approach
 197 - **Suboptimal Solutions**: Not comparing against known optimal solutions
 198
 199 ## Complexity & Performance Criticism Templates
 200
 201 ### For Asymptotic Issues
 202 ```
 203 Complexity Issue: [Specific asymptotic problem]
 204 Problem: [What's wrong with the complexity analysis]
 205 Impact: [How this affects performance or scalability]
 206 Evidence: [Specific mathematical analysis or measurements]
 207 Priority: [High/Medium/Low]
 208 ```
 209
 210 ### For Performance Issues
 211 ```
 212 Performance Issue: [Specific performance problem]
 213 Problem: [What's wrong with the performance characteristics]
 214 Impact: [How this affects efficiency or scalability]
 215 Evidence: [Specific benchmarks or measurements]
 216 Priority: [High/Medium/Low]
 217 ```
 218
 219 ### For Resource Issues
 220 ```
 221 Resource Issue: [Specific resource utilization problem]
 222 Problem: [What's wrong with resource usage]
 223 Impact: [How this affects scalability or efficiency]
 224 Evidence: [Specific resource measurements or analysis]
 225 Priority: [High/Medium/Low]
 226 ```
 227
 228 ### For Optimization Issues
 229 ```
 230 Optimization Issue: [Specific optimization opportunity]
 231 Problem: [What optimization is missing or suboptimal]
 232 Impact: [How this affects performance or efficiency]
 233 Evidence: [Specific analysis or comparison]
 234 Priority: [High/Medium/Low]
 235 ```
 236
 237 ## Complexity & Performance Criticism Best Practices
 238
 239 ### Do's
 240 - **Be Mathematically Precise**: Demand accurate complexity analysis
 241 - **Focus on Scalability**: Emphasize performance at scale
 242 - **Identify Bottlenecks**: Point out specific performance issues
 243 - **Suggest Optimizations**: Provide concrete improvement opportunities
 244 - **Compare to Standards**: Reference known optimal solutions
 245
 246 ### Don'ts
 247 - **Accept Vague Claims**: Don't accept imprecise complexity statements
 248 - **Ignore Constant Factors**: Don't overlook significant constant factors
 249 - **Skip Performance Analysis**: Don't ignore performance characteristics
 250 - **Accept Poor Scalability**: Don't settle for algorithms that don't scale
 251 - **Ignore Optimization**: Don't miss obvious improvement opportunities
 252
 253 ## Complexity & Performance Criticism Checklist
 254
 255 ### Asymptotic Assessment
 256 - [ ] Is the time complexity analysis complete and accurate?
 257 - [ ] Is the space complexity analyzed and justified?
 258 - [ ] Are Big O, Theta, and Omega all considered?
 259 - [ ] Are edge cases that affect complexity handled?
 260 - [ ] Are the complexity claims mathematically justified?
 261
 262 ### Performance Assessment
 263 - [ ] Are best, worst, and average cases analyzed?
 264 - [ ] Are constant factors considered when relevant?
 265 - [ ] Are performance bottlenecks identified?
 266 - [ ] Is performance analyzed across different input types?
 267 - [ ] Is the performance analysis complete and accurate?
 268
 269 ### Resource Assessment
 270 - [ ] How does memory usage scale with input size?
 271 - [ ] Are memory access patterns cache-friendly?
 272 - [ ] Does the algorithm scale efficiently to large inputs?
 273 - [ ] What are the resource consumption patterns?
 274 - [ ] Is resource utilization optimal?
 275
 276 ### Optimization Assessment
 277 - [ ] What optimization opportunities exist?
 278 - [ ] What is the cost-benefit ratio of potential optimizations?
 279 - [ ] Is this the most efficient algorithmic approach?
 280 - [ ] How does it compare to known optimal solutions?
 281 - [ ] Are there more efficient algorithms for this problem?
 282
 283 ## Complexity & Performance Evaluation Questions
 284
 285 ### For Any Algorithm
 286 1. **What is the precise time and space complexity?**
 287 2. **Are the complexity claims mathematically justified?**
 288 3. **What are the best, worst, and average case performances?**
 289 4. **How does the algorithm scale with input size?**
 290 5. **What are the performance bottlenecks?**
 291 6. **Are there optimization opportunities?**
 292 7. **How does it compare to known optimal solutions?**
 293 8. **What are the resource utilization characteristics?**
 294 9. **Is the performance analysis complete and accurate?**
 295 10. **What are the scalability limitations?**