Computing - Limits of Computation
AQA Computer Science 2022
See Also
Flashcards
Tractable and intractable problems
What are the time complexities for a tractable problem?
Polynomial time, e.g. $O(n^2)$ or $O(n^3)$
What is an intractable problem?
A problem where the computational demands grow so quickly that it’s impossible to solve non-theoretically.
What sort of time complexities does an intractable problem have?
Exponential.