a5c-ai complexity-analyzer
A specialized skill for automated analysis of algorithm time and space complexity, providing Big-O notation analysis, detailed derivations, and optimization recommendations.
Purpose
Analyze code and algorithms to determine:
- Time complexity (Big-O, Big-Omega, Big-Theta)
- Space complexity (auxiliary and total)
- Amortized complexity for data structure operations
- Complexity derivation with step-by-step reasoning
- Optimization opportunities and bottleneck identification
Capabilities
Core Analysis Features
Static Analysis
- Loop structure analysis (nested loops, dependent bounds)
- Recursive call tree analysis
- Function call graph traversal
- Branch condition impact analysis
Complexity Types
- Time Complexity: Worst, average, and best case analysis
- Space Complexity: Stack space, heap allocations, auxiliary space
- Amortized Analysis: Aggregate, accounting, and potential methods
- Recurrence Relations: Master theorem, substitution method
Output Formats
- Big-O notation with detailed derivation
- Complexity comparison tables
- Visual complexity graphs
- Optimization recommendations
Supported Languages
- Python (primary)
- C++ (full support)
- Java (full support)
- JavaScript/TypeScript (full support)
- Go, Rust, C (partial support)
Integration Options
MCP Servers
AST MCP Server - Advanced code structure analysis:
# Provides AST parsing and complexity analysis
npm install -g @angrysky56/ast-mcp-server
Code Analysis MCP - Natural language code exploration:
# Deep code understanding with data flow analysis
npm install -g code-analysis-mcp
Web-Based Tools
- TimeComplexity.ai - AI-powered runtime complexity
- Big-O Calculator - Web-based analysis
Usage
Analyze Code Complexity
# Analyze a Python function
complexity-analyzer analyze --file solution.py --function two_sum
# Analyze C++ code with detailed derivation
complexity-analyzer analyze --file solution.cpp --verbose
# Compare multiple implementations
complexity-analyzer compare --files impl1.py impl2.py impl3.py
Example Analysis
Input Code:
def find_pairs(arr, target):
n = len(arr)
result = []
for i in range(n): # O(n)
for j in range(i+1, n): # O(n-i) iterations
if arr[i] + arr[j] == target:
result.append((i, j))
return result
Analysis Output:
Time Complexity: O(n^2)
- Outer loop: n iterations
- Inner loop: (n-1) + (n-2) + ... + 1 = n(n-1)/2 iterations
- Total: O(n^2)
Space Complexity: O(k) where k = number of pairs found
- result array grows with matches
- Worst case: O(n^2) if all pairs match
Optimization Suggestion:
- Use hash table for O(n) time complexity
- Trade space for time: O(n) space
Output Schema
{
"analysis": {
"function": "string",
"language": "string",
"timeComplexity": {
"notation": "O(n^2)",
"bestCase": "O(1)",
"averageCase": "O(n^2)",
"worstCase": "O(n^2)",
"derivation": [
"Step 1: Outer loop runs n times",
"Step 2: Inner loop runs (n-1), (n-2), ..., 1 times",
"Step 3: Total = sum from 1 to n-1 = n(n-1)/2",
"Step 4: Simplify to O(n^2)"
]
},
"spaceComplexity": {
"notation": "O(n)",
"auxiliary": "O(n)",
"total": "O(n)",
"breakdown": {
"input": "O(n) - input array",
"result": "O(k) - output pairs",
"variables": "O(1) - loop counters"
}
},
"recommendations": [
{
"type": "optimization",
"description": "Use hash table approach",
"newComplexity": "O(n) time, O(n) space",
"tradeoff": "Space for time"
}
]
},
"metadata": {
"analyzedAt": "ISO8601 timestamp",
"confidence": "high|medium|low"
}
}
Analysis Patterns
Loop Analysis
| Pattern | Complexity | Example |
|---|---|---|
| Single loop | O(n) | for i in range(n) |
| Nested independent | O(n*m) | for i in n: for j in m |
| Nested dependent | O(n^2) | for i in n: for j in range(i) |
| Logarithmic | O(log n) | while n > 0: n //= 2 |
| Nested log | O(n log n) | for i in n: j=1; while j<n: j*=2 |
Recursion Analysis
| Pattern | Recurrence | Complexity |
|---|---|---|
| Linear | T(n) = T(n-1) + O(1) | O(n) |
| Binary | T(n) = T(n/2) + O(1) | O(log n) |
| Divide & Conquer | T(n) = 2T(n/2) + O(n) | O(n log n) |
| Exponential | T(n) = 2T(n-1) + O(1) | O(2^n) |
Master Theorem
For recurrence T(n) = aT(n/b) + f(n):
| Case | Condition | Complexity |
|---|---|---|
| 1 | f(n) = O(n^c) where c < log_b(a) | O(n^(log_b(a))) |
| 2 | f(n) = O(n^c) where c = log_b(a) | O(n^c log n) |
| 3 | f(n) = O(n^c) where c > log_b(a) | O(f(n)) |
Integration with Processes
This skill enhances:
complexity-optimization- Identify and fix complexity bottlenecksleetcode-problem-solving- Verify solution complexityalgorithm-implementation- Validate implementation efficiencycode-review- Complexity-focused code review
Common Complexity Classes
| Complexity | Name | Example |
|---|---|---|
| O(1) | Constant | Array access, hash lookup |
| O(log n) | Logarithmic | Binary search |
| O(n) | Linear | Array traversal |
| O(n log n) | Linearithmic | Merge sort, heap sort |
| O(n^2) | Quadratic | Nested loops, bubble sort |
| O(n^3) | Cubic | Matrix multiplication (naive) |
| O(2^n) | Exponential | Subsets, recursive fibonacci |
| O(n!) | Factorial | Permutations |
Error Handling
| Error | Cause | Resolution |
|---|---|---|
PARSE_ERROR |
Invalid syntax | Check code syntax |
UNSUPPORTED_CONSTRUCT |
Complex control flow | Simplify or annotate |
RECURSIVE_DEPTH |
Deep recursion | Provide base case hints |
AMBIGUOUS_BOUNDS |
Dynamic loop bounds | Annotate with constraints |
Best Practices
- Annotate Constraints: Provide variable ranges for accurate analysis
- Isolate Functions: Analyze one function at a time
- Consider Input Distribution: Specify if average case differs from worst
- Review Derivations: Verify step-by-step reasoning
- Test with Benchmarks: Validate theoretical analysis empirically