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

1. Static Analysis

   • Loop structure analysis (nested loops, dependent bounds)
   • Recursive call tree analysis
   • Function call graph traversal
   • Branch condition impact analysis

2. 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

3. 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

for i in range(n)

for i in n: for j in m

for i in n: for j in range(i)

while n > 0: n //= 2

for i in n: j=1; while j<n: j*=2

Recursion Analysis

Master Theorem

For recurrence T(n) = aT(n/b) + f(n):

Integration with Processes

This skill enhances:

• complexity-optimization

  - Identify and fix complexity bottlenecks

• leetcode-problem-solving

  - Verify solution complexity

• algorithm-implementation

  - Validate implementation efficiency

• code-review

  - Complexity-focused code review

Common Complexity Classes

Error Handling

PARSE_ERROR

UNSUPPORTED_CONSTRUCT

RECURSIVE_DEPTH

AMBIGUOUS_BOUNDS

Best Practices

1. Annotate Constraints: Provide variable ranges for accurate analysis
2. Isolate Functions: Analyze one function at a time
3. Consider Input Distribution: Specify if average case differs from worst
4. Review Derivations: Verify step-by-step reasoning
5. Test with Benchmarks: Validate theoretical analysis empirically

References

• AST MCP Server
• Code Analysis MCP
• TimeComplexity.ai
• Big-O Calculator
• MCP Reasoner