BigO Buddy 🚀

Deterministic Static-Analysis Time & Space Complexity Analyzer for VS Code

BigO Buddy is a high-performance, deterministic static analysis extension that calculates asymptotic Time and Space Complexity (Big-O) directly from your source code across 9 major programming languages.

🔒 Zero AI / Zero Cloud Dependency: BigO Buddy is NOT an AI wrapper. All Big-O calculations, recurrence solving, data-flow propagation, and algorithmic pattern detections are performed 100% locally and deterministically using AST (Abstract Syntax Tree) parsing and a language-independent Common Intermediate Representation (IR).

📑 Table of Contents

1. Supported Languages
2. Core Architecture
3. Mathematical & Symbolic Complexity Engine
4. Analysis Capabilities
   • Data Flow & Variable Sizing
   • Triangular & Dependent Loops
   • Recurrence Relations & Recursion
   • Space Complexity (Auxiliary vs Stack)
   • Standard Library & Collections
   • Algorithmic Pattern Detection
   • Hotspots & Optimization Advisor
   • Complexity Regression Detection
   • Exportable Reports (Markdown & JSON)
5. VS Code Interface
   • CodeLens
   • Hover Provider
   • Explorer TreeView
   • Diagnostics
6. Commands & Configuration
7. Limitations & Unknown Handling
8. Performance, Safety & Memory
9. Development & Testing
10. License

🌐 Supported Languages

🏗️ Core Architecture

The system enforces strict separation of concerns with a unified, language-independent pipeline:

Source Code (C++, C, Java, Python, JS, TS, C#, Go, Rust)
    ↓
Language Parser (Tree-sitter WASM / Native AST)
    ↓
Language Adapter (Language-specific AST Mapping)
    ↓
Language-Independent Common IR
    ↓
Analysis Engine (Loop, Recursion, Branch, Space, Data Flow, Patterns, Call Graph)
    ↓
Structured Complexity Engine (Exact Symbolic +, ×, max)
    ↓
Explanation & Confidence System (Deterministic Audit Trail)
    ↓
VS Code Presentation Layer (CodeLens + Hover + Sidebar TreeView + Diagnostics + Reports)

Strict Architectural Invariant: The generic complexity engine and space analyzers contain zero language-specific AST node names. All language peculiarities are isolated inside dedicated Language Adapters.

📐 Mathematical & Symbolic Complexity Engine

BigO Buddy models complexity as structured mathematical objects rather than raw strings:

$$\text{Complexity} = \langle \text{kind}, \text{polyDeg}, \text{logDeg}, \text{expBase}, \text{factorial}, \text{variables}, \text{isUnknown} \rangle$$

Algebraic Operations

• Addition (Sequential Execution): $\mathcal{O}(f) + \mathcal{O}(g) = \max(\mathcal{O}(f), \mathcal{O}(g))$
  • Example: $O(n) + O(n^2) \rightarrow O(n^2)$
• Multiplication (Nested Execution): $\mathcal{O}(f) \times \mathcal{O}(g)$
  • Example: $O(n) \times O(\log n) \rightarrow O(n \log n)$
  • Example: $O(n^2) \times O(\log n) \rightarrow O(n^2 \log n)$
  • Example: $O(1) \times O(n) \rightarrow O(n)$
• Dominance Hierarchy: $$\mathcal{O}(1) < \mathcal{O}(\log n) < \mathcal{O}(n) < \mathcal{O}(n \log n) < \mathcal{O}(n^2) < \mathcal{O}(n^3) < \mathcal{O}(n^k) < \mathcal{O}(2^n) < \mathcal{O}(a^n) < \mathcal{O}(n!)$$

🔬 Analysis Capabilities

1. Data Flow & Variable Sizing

Tracks variable assignments and propagates sizes symbolically:

int m = n * n;
for (int i = 0; i < m; i++) {
    // Correctly deduced as O(n²)
}

2. Triangular & Dependent Loops

Accurately sums dependent loops without false over-multiplication:

for (int i = 0; i < n; i++) {
    for (int j = i; j < n; j++) {
        // Inner loop runs (n - i) times -> (n*(n+1))/2 -> O(n²)
    }
}

3. Recurrence Relations & Recursion

Analyzes recursive function call graphs using rigorous recurrence templates:

• $T(n) = T(n - 1) + O(1) \implies \mathcal{O}(n)$
• $T(n) = T(n / 2) + O(1) \implies \mathcal{O}(\log n)$
• $T(n) = 2T(n / 2) + O(n) \implies \mathcal{O}(n \log n)$ (Merge Sort)
• $T(n) = 2T(n / 2) + O(1) \implies \mathcal{O}(n)$
• $T(n) = 2T(n - 1) + O(1) \implies \mathcal{O}(2^n)$ (Fibonacci)
• $T(n) = nT(n - 1) + O(1) \implies \mathcal{O}(n!)$ (Permutations)

4. Space Complexity Analysis

Time and space are analyzed independently:

• Auxiliary Heap Allocations: new int[n], vector<int>(n), int matrix[n][n] $\rightarrow O(n^2)$
• Call Stack Depth: Binary recursion fib(n) has $O(2^n)$ time but only $O(n)$ stack space.
• Accumulating Containers: Detects containers growing inside loops (v.push_back() inside loop $\rightarrow O(n)$ space).

5. Standard Library & Collections

Built-in knowledge of collection operations across STL, Java Collections, Python builtins, JavaScript Arrays, C# collections, Go slices/maps, and Rust Vec/HashMap.

6. Algorithmic Pattern Detection

Multi-signal structural pattern detector with confidence metrics:

• Two Pointer: Loop pointer comparisons (left < right) combined with bidirectional updates (left++, right--).
• Binary Search: Halving interval updates (low = mid + 1, high = mid - 1) inside logarithmic conditions.
• Sliding Window: Window state tracking with boundary expansion and contraction.
• Prefix Sum: Accumulator array patterns with element difference range queries.
• Dynamic Programming: 2D/1D table allocations with subproblem recurrence lookups.
• Divide and Conquer: Subproblem splitting and recursive combinations.

7. Hotspots & Optimization Advisor

• Hotspot Ranking: Categorizes code blocks by asymptotic severity.
• Conservative Suggestions: Generates safe, non-prescriptive recommendations (e.g. "Consider hoisting sort operations outside loops" or "Consider using a HashSet/HashMap for $O(1)$ lookups").

8. Complexity Diff & Regression Detection

Potential complexity regression detected in solve():
  Previous: O(n)
  Current:  O(n²)

9. Exportable Reports

Generate comprehensive analysis reports in Markdown and JSON with visual ASCII complexity distributions and hotspot breakdowns.

🖥️ VS Code Interface

CodeLens

Displays inline complexity metrics directly above function signatures and major loop constructs:

Time: O(n²) | Space: O(1) [High Confidence]
void bubbleSort(vector<int>& arr) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n - i - 1; j++) { ... }
    }
}

Hover Provider

Hovering over any function or loop displays a rich breakdown:

### 🚀 BigO Buddy Complexity Analysis

- **Time Complexity**: `O(n²)`
- **Space Complexity**: `O(1)`
- **Confidence**: `High`

**Why:**
- Outer loop contributes `O(n)`
- Inner loop contributes `O(n)`
- Nested multiplication: `O(n) × O(n) = O(n²)`

**Algorithmic Pattern**:
- Nested Iteration (Hotspot)

Native Sidebar TreeView

Access the dedicated BigO Buddy Explorer view in the Activity Bar to inspect:

• 📊 Document Overview: Overall time & space complexity.
• ⚡ Functions & Loops: Asymptotic breakdowns per function.
• 🔥 Complexity Hotspots: Bottlenecks sorted by severity.
• 💡 Optimization Suggestions: Actionable structural recommendations.
• 🧠 Detected Patterns: Identified algorithms with confidence tags.

⚙️ Commands & Configuration

Commands

• BigO Buddy: Analyze Complexity (bigoBuddy.analyzeComplexity): Analyzes the active editor document or current function.
• BigO Buddy: Analyze Current Function (bigoBuddy.analyzeFunction): Focuses complexity analysis on the function enclosing the cursor.
• BigO Buddy: Analyze File (bigoBuddy.analyzeFile): Analyzes the entire active source file.
• BigO Buddy: Clear Analysis (bigoBuddy.clearAnalysis): Clears analysis caches, diagnostics, and TreeView state.
• BigO Buddy: Analyze Project (bigoBuddy.analyzeProject): Scans all supported files in workspace and computes call graph summaries.
• BigO Buddy: Compare Complexity (bigoBuddy.compareComplexity): Compares complexity across code edits to detect regressions.
• BigO Buddy: Export Complexity Report (bigoBuddy.exportReport): Generates a Markdown audit report.

Settings (settings.json)

{
  "bigOBuddy.showCodeLens": true,
  "bigOBuddy.showFunctionCodeLens": true,
  "bigOBuddy.showLoopCodeLens": true,
  "bigOBuddy.showHover": true,
  "bigOBuddy.showExplanation": true,
  "bigOBuddy.showConfidence": true,
  "bigOBuddy.showHotspots": true,
  "bigOBuddy.showSuggestions": true,
  "bigOBuddy.generateReports": true,
  "bigOBuddy.detectPatterns": true,
  "bigOBuddy.analysisDepth": "deep",
  "bigOBuddy.showRegression": true,
  "bigOBuddy.debounceMs": 350,
  "bigOBuddy.maxFileSize": 524288,
  "bigOBuddy.maxAnalysisTime": 5000,
  "bigOBuddy.enableDiffAware": true
}

🔒 Privacy & Safety

• 100% Local Static Analysis: BigO Buddy performs all parsing, AST transformation, and complexity calculations entirely on your local machine.
• Zero Cloud & Zero AI Dependency: No source code, snippets, or metadata leave your environment.
• Zero Code Execution: User code is statically analyzed and never executed (eval, child processes, and dynamic runtimes are strictly forbidden).

⚠️ Limitations & Unknown Handling

BigO Buddy is a deterministic static analyzer. It operates under mathematically sound principles and never guesses when evidence is insufficient:

1. Halting Problem & Decidability: Static analysis cannot determine exact asymptotic bounds for arbitrary recursive programs or non-linear loops (e.g. Collatz Conjecture).
2. Opaque External Calls: Calls to unanalyzed third-party libraries, dynamic Reflection, or external binaries are marked with Unknown complexity and explicit rationale.
3. Dynamic Typing & Metaprogramming: Dynamic Python/JS runtime attribute mutation (eval(), dynamic getattr()) limits static deduction confidence.
4. Worst-Case vs Average-Case: By default, BigO Buddy calculates worst-case asymptotic bounds. Hash table collisions, amortized vectors, and randomized quickselect are noted accordingly.
5. Zero Code Execution: BigO Buddy never executes user code under any circumstance.

⚡ Performance, Safety & Memory

• LRU Bounded Caches: Multi-tier caching (ASTCache, IRCache, AnalysisCache) with strict capacity limits to avoid memory leaks.
• Cancellation Tokens: Asynchronous debounced processing discards obsolete analysis runs if the user continues typing.
• Large-File Protection: Files exceeding configurable thresholds (default: 5MB or 10,000 lines) are protected against runaway parsing.
• Fault-Tolerant Parsing: Syntax errors or incomplete code blocks are caught gracefully, producing partial analysis without crashing the VS Code Extension Host.

🧪 Development & Testing

Build & Compile

npm install
npm run compile

Run Full Regression Suite

npm test

The test corpus includes 21 comprehensive test suites covering over 200 unit and integration tests across all 9 languages, regression guards, and false-positive benchmarks.

📄 License

MIT License © 2026 Mayank Padmani