tc-analyzer 0.1.0

Python time complexity analysis library using AST parsing

tc-analyzer

A Python library for analyzing time complexity of code through AST parsing.

Installation

pip install tc-analyzer

Usage

from tc_analyzer import analyze

# Analyze code string
code = '''
def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(0, n-i-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
    return arr
'''

result = analyze(code)
print(result.functions[0].complexity.overall)  # O(n^2)
print(result.functions[0].algorithm_type)      # sorting

# Analyze file
result = analyze('/path/to/your/file.py')

# Analyze specific function
result = analyze(code, target='function:my_func')

Features

• Loop nesting detection (O(n), O(n^2), O(n^3), etc.)
• Built-in function complexity (sorted, max, len, etc.)
• Data structure operation complexity (list.append, dict.get, etc.)
• Recursion analysis (linear, divide-and-conquer, exponential)
• Algorithm pattern recognition (sorting, search, dynamic programming)
• Line-by-line complexity contributions

Output Structure

class FunctionAnalysis:
    name: str                          # Function name
    complexity: ComplexityResult       # O(n) with confidence
    lines: List[LineContribution]      # Line-by-line breakdown
    loops: int                         # Nesting depth
    recursion: bool                    # Is recursive
    algorithm_type: str                # 'sorting', 'search', 'dp', etc.

Supported Complexity Patterns

Pattern	Detected
Nested loops	O(n^k)
Built-in sorted	O(n log n)
Linear recursion	O(n)
Binary recursion	O(2^n)
Divide by 2 recursion	O(log n)

Examples

Loop Detection

code = '''
def process(arr):
    for i in arr:
        for j in arr:
            print(i, j)
'''
result = analyze(code)
# Output: O(n^2) - 2 nested loops detected

Built-in Function

code = '''
def sort_list(arr):
    return sorted(arr)
'''
result = analyze(code)
# Output: O(n log n) - built-in function with O(n log n)

Recursion

code = '''
def factorial(n):
    if n <= 1:
        return 1
    return n * factorial(n - 1)
'''
result = analyze(code)
# Output: O(n) - recursive function with O(n) complexity

Algorithm Recognition

code = '''
def binary_search(arr, low, high, x):
    if high >= low:
        mid = (low + high) // 2
        if arr[mid] == x:
            return mid
        ...
'''
result = analyze(code)
# Output: algorithm_type = 'search'

License

MIT