# Complexity

> Analyzes algorithm time and space complexity, classifies problems by complexity classes, proves NP-completeness, and designs approximation algorithms.

- Skill: `neuralblitz/complexity` (Agent Skill)
- Install (CLI): `npx skillmds@latest add neuralblitz/complexity`
- Raw SKILL.md: https://api.skillmd.com/api/skills/neuralblitz/complexity/raw
- Safety review: PASS (external: skill-scanner PASS, skillspector PASS)
- Works with: Claude Code, Claude.ai, OpenAI Codex
- Category: AI & ML
- Tags: Algorithm Analysis, Approximation Algorithms, Big O Notation, Complexity Classes, Np Completeness, Randomized Algorithms
- License: MIT
- Author: NeuralBlitz (https://skillmd.com/u/neuralblitz)
- Updated: 2026-08-22
- Page: https://skillmd.com/skills/neuralblitz/complexity

---

## 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