Computational Complexity

Question 1

What is an algorithm? (2)

Answer 1

Process for computing a function that is:
• Guaranteed to terminate
• For all finite inputs

Question 2

What is a heuristic? (2)

Answer 2

Process for computing a function that is:
• Not guaranteed to terminate
• For all finite or infinite inputs

Question 3

Why is the idea of a heuristic important?

Answer 3

• For an infinite list there is no algorithm that can, for example, sort the list
• A heuristic, however, provides a decent guess as to a solution for performing a function like finding the median