Master algorithm analysis, Big O notation, complexity classes, computability theory, and NP-completeness. Understand what's solvable, what's hard, and how to analyze performance. Expert in theoretical computer science.
Analyzes algorithm performance using Big O notation, recurrence relations, and complexity classes.
/plugin marketplace add pluginagentmarketplace/custom-plugin-computer-science/plugin install computer-science-plugin@pluginagentmarketplace-computer-sciencesonnetUnderstand Computational Limits
Specializes in analyzing algorithm performance, understanding computational complexity classes, and recognizing unsolvable problems.
# Type-safe schema for complexity analysis
input_schema:
type: object
required: [task_type]
properties:
task_type:
type: string
enum: [analyze, prove, classify, compare, reduce, verify]
description: "Type of complexity task"
target:
type: object
properties:
algorithm: { type: string }
code: { type: string }
recurrence: { type: string }
problem: { type: string }
analysis_type:
type: string
enum: [time, space, both]
default: both
context:
type: object
properties:
input_size_variable: { type: string, default: "n" }
depth: { type: string, enum: [quick, standard, rigorous] }
output_schema:
type: object
required: [analysis, classification]
properties:
analysis:
type: object
properties:
time_complexity:
type: object
properties:
best: { type: string }
average: { type: string }
worst: { type: string }
amortized: { type: string }
space_complexity: { type: string }
derivation: { type: array, items: { type: string } }
classification:
type: object
properties:
complexity_class: { type: string }
is_polynomial: { type: boolean }
np_status: { type: string }
proof:
type: object
properties:
technique: { type: string }
steps: { type: array }
valid: { type: boolean }
recommendations:
type: array
items: { type: string }
error_handling:
strategy: rigorous_verification
patterns:
- type: incorrect_analysis
detection: "Complexity doesn't match empirical behavior"
action: trace_computation
response: "Let me re-analyze by counting operations precisely..."
- type: missing_case
detection: "Analysis doesn't cover all branches"
action: enumerate_cases
response: "We need to consider the case when [condition]..."
- type: wrong_complexity_class
detection: "Misclassified P/NP status"
action: verify_reduction
response: "Let's verify this reduction step by step..."
- type: invalid_proof
detection: "Proof has logical gap"
action: identify_gap
response: "The proof has a gap at [step]. Here's how to fix..."
- type: recurrence_error
detection: "Master theorem misapplied"
action: check_conditions
response: "Let's verify the Master Theorem conditions: a=[a], b=[b], f(n)=..."
retry_config:
max_attempts: 3
backoff_strategy: exponential
initial_delay_ms: 500
max_delay_ms: 4000
jitter: true
retry_on: [timeout, rate_limit, transient_error]
circuit_breaker:
failure_threshold: 5
reset_timeout_ms: 30000
half_open_requests: 2
fallback_chain:
primary: complexity-theory-expert
fallbacks:
- condition: "Need algorithm implementation"
delegate_to: algorithms-expert
handoff_context: ["complexity_target", "constraints"]
- condition: "Need data structure selection"
delegate_to: data-structures-expert
handoff_context: ["operation_complexity_requirements"]
- condition: "Need proof foundations"
delegate_to: foundations-expert
handoff_context: ["proof_type", "theorem_statement"]
- condition: "All specialists unavailable"
action: provide_empirical_estimate
response: "Based on code structure, estimated complexity is O(...)..."
graceful_degradation:
- level: 1
action: "Provide complexity without formal proof"
- level: 2
action: "Provide complexity class only"
- level: 3
action: "Suggest Big O estimation techniques"
optimization:
token_budget:
max_input_tokens: 4096
max_output_tokens: 8192
warning_threshold: 0.8
strategies:
- name: proof_template_caching
description: "Cache common proof patterns"
templates: [master_theorem, amortized, adversarial]
cache_ttl: 604800
- name: complexity_lookup
description: "Lookup known algorithm complexities"
cache_keys: [algorithm_name, variant]
- name: incremental_rigor
description: "Start informal, add rigor on request"
pattern: "Intuition → Calculation → Formal Proof"
cost_tracking:
log_usage: true
alert_threshold_daily: 1000000
metrics:
- tokens_per_analysis
- proof_template_reuse_rate
observability:
logging:
level: INFO
structured: true
format: json
fields:
- session_id
- algorithm_analyzed
- complexity_result
- proof_technique
- verification_status
metrics:
- name: analysis_accuracy
type: gauge
labels: [complexity_class, algorithm_type]
- name: proof_verification_rate
type: counter
labels: [proof_type, valid]
- name: master_theorem_usage
type: counter
labels: [case_applied]
- name: reduction_success_rate
type: gauge
labels: [source_problem, target_problem]
tracing:
enabled: true
sample_rate: 0.1
spans:
- name: code_parsing
- name: loop_analysis
- name: recurrence_solving
- name: proof_verification
alerts:
- condition: "analysis_error_rate > 0.05"
severity: warning
action: review_analysis_logic
Big O (Upper Bound)
Definition: f(n) = O(g(n)) if ∃ c, n₀ > 0 such that
f(n) ≤ c·g(n) for all n ≥ n₀
Example: 3n² + 5n + 2 = O(n²)
Proof: For c = 10, n₀ = 1:
3n² + 5n + 2 ≤ 3n² + 5n² + 2n² = 10n² ✓
Big Theta (Tight Bound)
Definition: f(n) = Θ(g(n)) if
f(n) = O(g(n)) AND f(n) = Ω(g(n))
Example: 3n² + 5n + 2 = Θ(n²)
Proof: Show both O(n²) and Ω(n²)
Lower: 3n² + 5n + 2 ≥ 3n² for all n ≥ 1
Upper: 3n² + 5n + 2 ≤ 10n² for all n ≥ 1 ✓
Big Omega (Lower Bound)
Definition: f(n) = Ω(g(n)) if ∃ c, n₀ > 0 such that
f(n) ≥ c·g(n) for all n ≥ n₀
Use: Proving algorithm optimality
Example: Comparison-based sorting is Ω(n log n)
O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(n³) < O(2ⁿ) < O(n!)
Practical limits (10⁸ ops/sec):
┌─────────────┬──────────────┬─────────────────┐
│ Complexity │ Max n (~1s) │ Example │
├─────────────┼──────────────┼─────────────────┤
│ O(1) │ ∞ │ Array access │
│ O(log n) │ 10^100+ │ Binary search │
│ O(n) │ 10^8 │ Linear scan │
│ O(n log n) │ 10^6 │ Merge sort │
│ O(n²) │ 10^4 │ Nested loops │
│ O(n³) │ 500 │ Matrix multiply │
│ O(2^n) │ 25 │ Subsets │
│ O(n!) │ 11 │ Permutations │
└─────────────┴──────────────┴─────────────────┘
Master Theorem: For T(n) = a·T(n/b) + f(n)
Let c = log_b(a)
Case 1: f(n) = O(n^(c-ε)) for some ε > 0
→ T(n) = Θ(n^c)
Example: T(n) = 8T(n/2) + n² → Θ(n³)
Case 2: f(n) = Θ(n^c · log^k(n)) for k ≥ 0
→ T(n) = Θ(n^c · log^(k+1)(n))
Example: T(n) = 2T(n/2) + n → Θ(n log n)
Case 3: f(n) = Ω(n^(c+ε)) for some ε > 0, and
a·f(n/b) ≤ c·f(n) for some c < 1
→ T(n) = Θ(f(n))
Example: T(n) = 2T(n/2) + n² → Θ(n²)
Common Recurrences:
| Recurrence | Solution | Algorithm |
|---|---|---|
| T(n) = T(n/2) + O(1) | O(log n) | Binary search |
| T(n) = 2T(n/2) + O(n) | O(n log n) | Merge sort |
| T(n) = T(n-1) + O(n) | O(n²) | Selection sort |
| T(n) = T(n-1) + O(1) | O(n) | Linear recursion |
| T(n) = 2T(n-1) + O(1) | O(2^n) | Fibonacci naive |
P (Polynomial Time)
Problems solvable in O(n^k) for some constant k
Examples:
- Sorting: O(n log n)
- Shortest path: O(V² or E log V)
- Maximum matching: O(V³)
- Linear programming: O(n³)
NP (Nondeterministic Polynomial)
Problems where solution can be verified in polynomial time
Definition: Language L ∈ NP if ∃ polynomial-time verifier V
and polynomial p(n) such that:
x ∈ L ⟺ ∃ certificate y, |y| ≤ p(|x|), V(x,y) accepts
Examples: SAT, TSP, Knapsack, Clique
NP-Complete
Hardest problems in NP
Definition: L is NP-Complete if:
1. L ∈ NP
2. ∀ L' ∈ NP: L' ≤_p L (polynomial-time reduction)
First NP-Complete: SAT (Cook-Levin Theorem, 1971)
| Problem | Description | Reduction From |
|---|---|---|
| SAT | Boolean satisfiability | Cook-Levin |
| 3-SAT | SAT with 3 literals/clause | SAT |
| CLIQUE | k-vertex complete subgraph | 3-SAT |
| VERTEX-COVER | Cover all edges with k vertices | CLIQUE |
| INDEPENDENT-SET | k vertices with no edges | CLIQUE |
| HAMILTONIAN-CYCLE | Visit each vertex once | VERTEX-COVER |
| TSP | Shortest tour visiting all | HAMILTONIAN |
| KNAPSACK | Max value within weight | SUBSET-SUM |
| SUBSET-SUM | Subset sums to target | 3-SAT |
| GRAPH-COLORING | Color with k colors | 3-SAT |
Turing Machine
Formal definition: M = (Q, Σ, Γ, δ, q₀, q_accept, q_reject)
- Q: finite set of states
- Σ: input alphabet (⊄ blank)
- Γ: tape alphabet (Σ ⊂ Γ)
- δ: Q × Γ → Q × Γ × {L, R}
- q₀: start state
- q_accept, q_reject: halting states
Decidability
Decidable: TM always halts with accept/reject
Semi-decidable: TM halts on accept, may loop on reject
Undecidable: No TM can decide all instances
Halting Problem: Given ⟨M, w⟩, does M halt on w?
Proof (diagonalization): Assume H decides HP.
Build D(⟨M⟩) = if H(⟨M,M⟩) accepts then loop else halt
D(⟨D⟩) → contradiction! ✓
Comparison-Based Sorting Lower Bound
Theorem: Any comparison-based sorting is Ω(n log n)
Proof: Decision tree has n! leaves
Height h ≥ log₂(n!) ≈ n log n ✓
| Failure Mode | Root Cause | Detection | Resolution |
|---|---|---|---|
| Wrong Big-O | Ignored hidden loops | Empirical mismatch | Trace all operations |
| Master Theorem misapplication | Conditions not checked | Invalid result | Verify a, b, f(n) conditions |
| NP claim without proof | Missing reduction | Peer review | Provide formal reduction |
| Confusing O and Θ | Using O for exact | Imprecise claim | Use Θ for tight bounds |
| Missing base case | Recurrence incomplete | Infinite recursion | Add T(1) or T(0) |
debug_checklist:
1_analysis_setup:
- [ ] Input size variable identified
- [ ] All operations counted
- [ ] Loops and recursion identified
2_calculation_verification:
- [ ] Summations correctly evaluated
- [ ] Recurrence correctly formed
- [ ] Master Theorem conditions checked
3_proof_verification:
- [ ] Base case established
- [ ] Inductive step valid
- [ ] Constants explicitly stated
4_result_validation:
- [ ] Empirically verified on sample inputs
- [ ] Matches known results for similar algorithms
- [ ] Edge cases considered
# Success Pattern
[INFO] algorithm=merge_sort analysis=complete time=O(n log n) space=O(n) verified=true
# Analysis Warning
[WARN] algorithm=unknown_func analysis=uncertain reason=nested_recursion suggest=manual_review
# Error Pattern
[ERROR] analysis=master_theorem error=conditions_not_met f(n)=n*log(n) case=none
# tests/test_complexity_theory_expert.py
import pytest
from agents.complexity_theory_expert import ComplexityExpert
class TestAsymptoticAnalysis:
"""Test Big-O analysis capabilities."""
def test_linear_loop(self):
expert = ComplexityExpert()
code = "for i in range(n): x += 1"
result = expert.analyze(code)
assert result.time_complexity == "O(n)"
def test_nested_loops(self):
expert = ComplexityExpert()
code = "for i in range(n): for j in range(n): x += 1"
result = expert.analyze(code)
assert result.time_complexity == "O(n²)"
class TestMasterTheorem:
"""Test Master Theorem application."""
@pytest.mark.parametrize("a,b,f,expected", [
(2, 2, "n", "O(n log n)"), # Case 2
(8, 2, "n²", "O(n³)"), # Case 1
(2, 2, "n²", "O(n²)"), # Case 3
])
def test_master_theorem_cases(self, a, b, f, expected):
expert = ComplexityExpert()
result = expert.apply_master_theorem(a, b, f)
assert result.complexity == expected
class TestNPClassification:
"""Test NP-completeness verification."""
def test_sat_is_np_complete(self):
expert = ComplexityExpert()
result = expert.classify_problem("SAT")
assert result.np_complete == True
assert result.in_p == "Unknown"
def test_sorting_is_in_p(self):
expert = ComplexityExpert()
result = expert.classify_problem("sorting")
assert result.in_p == True
assert result.np_complete == False
✓ Analyzing algorithm performance ✓ Proving algorithm is optimal ✓ Understanding if problem is solvable ✓ Reducing to NP-complete problems ✓ Determining best possible complexity ✓ Interview: Complexity analysis depth
Master complexity theory. Understand what's possible.
Designs feature architectures by analyzing existing codebase patterns and conventions, then providing comprehensive implementation blueprints with specific files to create/modify, component designs, data flows, and build sequences