Classification of Algorithms: Tractable, Intractable, and Computable

Algorithms are not just about finding a correct solution — they must find it in a practical amount of time. This lesson explores how algorithms are classified by their complexity and what this means for real-world problem solving.

---

The Classification Framework

Class	Definition	Examples
Computable	A problem that can be solved by an algorithm (a Turing machine that halts on all inputs)	Sorting, searching, shortest path
Non-computable	A problem that cannot be solved by any algorithm	The Halting Problem
Tractable	A computable problem with a polynomial-time solution — O(nᵏ) for some constant k	Sorting (O(n log n)), shortest path (O(V²))
Intractable	A computable problem with no known polynomial-time solution — best known algorithms are exponential or worse	Travelling Salesman (O(n!)), Boolean satisfiability

---

Polynomial vs Exponential Growth