You are viewing a free preview of this lesson.
Subscribe to unlock all 10 lessons in this course and every other course on LearningBro.
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.
| 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 |
Subscribe to continue reading
Get full access to this lesson and all 10 lessons in this course.