3.17 Algorithmic Efficiency

Problems

Generally speaking, a problem is a task that an algorithm is trying to solve**.** An instance of the problem is a problem with a specific input**.** The example the College Board CED gives is that sorting is a problem while sorting the list [2, 3, 1, 7] is an instance of the problem. 

Some examples of common problem types are decision problems and optimization problems. Decision problems have a yes/no answer, while optimization problems ask what the best solution is to the task at hand. 

Finding out if a number is prime is a decision problem, because you can answer that question with a yes or a no. Finding the shortest path between two cities, on the other hand, is considered an optimization problem. It wants the best answer (in this case the shortest), not just an answer.

It's more optimal for a computer to find the best route than it is for you to attempt it with a map. Image source: Moonrise Kingdom/GIPHY

Efficiency

An algorithm's efficiency is an estimate of how many computational resources (like power, memory or time) it uses. It's officially expressed as a function of the size of the input. This just means that the efficiency varies based on the input size—the bigger the input, the more resources it'll use, and vice versa. There are formal equations to calculate it, but you don't have to know them for the AP CSP test. 

Informally, efficiency is measured by determining how many times a statement or statement group executes. Algorithms that run with a polynomial efficiency or lower are said to run in a reasonable amount of time while algorithms that run with an exponential or factorial efficiency run in an unreasonable amount of time.

Different correct algorithms for the same problem can have different efficiencies, just like how different ways to solve a problem can take longer or shorter or be more or less effective.

Some problems can't be solved in a reasonable amount of time. In this case, computers turn to an approximate solution. The technique to find this approximate solution is known as a heuristic.