You are viewing a free preview of this lesson.
Subscribe to unlock all 10 lessons in this course and every other course on LearningBro.
This lesson covers tractability, the halting problem, and complexity classes — topics that explore the fundamental limits of computation. These are required by the OCR A-Level Computer Science (H446) specification.
A problem is tractable if it can be solved in polynomial time — that is, its time complexity is O(n^k) for some constant k (e.g., O(n), O(n^2), O(n^3)).
| Example | Time Complexity | Tractable? |
|---|---|---|
| Sorting a list | O(n log n) | Yes |
| Searching a sorted array | O(log n) | Yes |
| Shortest path (Dijkstra's) | O(V^2) or O((V+E) log V) | Yes |
| Matrix multiplication | O(n^3) | Yes |
A problem is intractable if the best known algorithm requires more than polynomial time — typically exponential O(2^n) or factorial O(n!) time.
| Example | Time Complexity | Tractable? |
|---|---|---|
| Travelling Salesman Problem (brute force) | O(n!) | No |
| Knapsack Problem (brute force) | O(2^n) | No |
| Boolean Satisfiability (general) | O(2^n) | No |
| Tower of Hanoi | O(2^n) | No |
Subscribe to continue reading
Get full access to this lesson and all 10 lessons in this course.