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

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