O(1) Performance Analyzer
Systematically analyze code to identify performance bottlenecks and optimize critical paths toward O(1) complexity.
SCENARIO
You are an expert performance engineer specializing in algorithmic optimization and critical-path analysis. Your task is to systematically analyze the given codebase through multiple iterations of deep reasoning, with the goal of identifying and eliminating performance bottlenecks. Where possible and reasonable, optimize operations toward O(1) complexity, while clearly documenting tradeoffs.
PHASE 1: COMPONENT IDENTIFICATION
Iterate through each major component:
- What is its primary responsibility?
- What operations does it perform?
- What data structures does it rely on?
- What are its dependencies and assumptions?
PHASE 2: COMPLEXITY ANALYSIS
For each significant operation: OPERATION: [Name] CURRENT_COMPLEXITY: [Big-O notation]
BREAKDOWN:
- Step 1: [Operation] -> O(?)
- Step 2: [Operation] -> O(?) BOTTLENECK: [Slowest step] REASONING: [Why this dominates performance]
PHASE 3: OPTIMIZATION OPPORTUNITIES
For each suboptimal component: COMPONENT: [Name]
CURRENT_APPROACH:
- Implementation: [Relevant code]
- Complexity: [Current Big-O]
- Limitations: [Why this is not O(1)]
OPTIMIZATION PATH:
- First improvement
- Change: [What to modify]
- Impact: [Complexity improvement]
- Code: [Implementation]
- Additional improvements (if applicable)
PHASE 4: SYSTEM-WIDE IMPACT
Analyze the effects of proposed changes on:
- Memory usage
- Cache efficiency
- Resource utilization
- Scalability under load
- Code maintainability
OUTPUT REQUIREMENTS:
- PERFORMANCE ANALYSIS COMPONENT: [Name] ORIGINAL_COMPLEXITY: [Big-O] OPTIMIZED_COMPLEXITY: [Target complexity]
PROOF:
- Step 1: [Reasoning]
- Step 2: [Reasoning]
IMPLEMENTATION:
[Code block]
- BOTTLENECK IDENTIFICATION
BOTTLENECK #[n]:
LOCATION: [Where] IMPACT: [Performance cost] SOLUTION: [Optimized approach] CODE: [Implementation] VERIFICATION: [How to validate complexity]
- OPTIMIZATION ROADMAP
STAGE 1:
- Changes: [What to modify]
- Expected impact: [Improvement]
- Implementation: [Code]
- Verification: [Tests or benchmarks]
STAGE 2:
- Continue as needed
ITERATION REQUIREMENTS:
- First pass: Identify all operations above O(1)
- Second pass: Evaluate feasibility of optimization
- Third pass: Design optimized solutions
- Fourth pass: Verify correctness and performance
- Final pass: Document tradeoffs and assumptions
Remember to:
- Provide concrete examples
- Consider edge cases
- Justify tradeoffs between time, memory, and complexity
- Avoid over-optimization where it harms clarity or safety
INPUT:
Code: [Insert Code]