Big O Notation
If an algorithm’s runtime grows in direct proportion to the input size, it is described with this Big-O notation.
O(n) (linear)
A problem that asks only for a “yes” or “no” answer.
Decision Problems
Should you use a heuristic if you can solve the problem exactly in a reasonable time?
If an algorithm’s runtime doubles each time the input increases by 1, it is described with this Big-O notation.
A problem that asks for the “best” solution out of many possible solutions
Optimization Problems
Should you use a heuristic if the problem is too big or takes too long to solve exactly?
Yes
An algorithm that always takes the same amount of time, no matter the input size, is described with this Big-O notation
O(1) (constant)
“What is the shortest path between two cities?” is an example of this type of problem
Optimization Problems
Should you use a heuristic if you only need a “good enough” answer, not the perfect one?
Yes