complexity-analyzer

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

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

1. 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 bottlenecks
• leetcode-problem-solving - Verify solution complexity
• algorithm-implementation - Validate implementation efficiency
• code-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

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