complexity
Installation
SKILL.md
What I do
- Analyze time and space complexity of algorithms
- Classify problems by complexity classes (P, NP, PSPACE)
- Prove NP-completeness and NP-hardness
- Apply asymptotic notation (Big-O, Ω, Θ)
- Design approximation algorithms
- Analyze randomized algorithm complexity
When to use me
When optimizing algorithms, proving computational limits, or classifying problem difficulty.
Key Concepts
- Big-O: f = O(g) if ∃c,n₀: f(n) ≤ cg(n) for n ≥ n₀
- P: Problems solvable in polynomial time
- NP: Problems verifiable in polynomial time
- NP-Complete: Hardest problems in NP, polynomial-time reduction
- Space Complexity: Memory requirements vs input size
- Polynomial-Time Reduction: Transform one problem to another preserving complexity