3.17 Algorithmic Efficiency

Enduring Understanding

There exist problems that computers cannot solve, and even when a computer can solve a problem, it may not be able to do so in a reasonable amount of time.

Learning Objective

For determining the efficiency of an algorithm:

a. Explain the difference between algorithms that run in reasonable time and those that do not.

b. Identify situations where a heuristic solution may be more appropriate.

Essential Knowledge

A problem is a general description of a task that can (or cannot) be solved algorithmically. An instance of a problem also includes specific input. For example, sorting is a problem; sorting the list (2,3,1,7) is an instance of the problem.

A decision problem is a problem with a yes/no answer (e.g., is there a path from A to B?). An optimization problem is a problem with the goal of finding the “best” solution among many (e.g., what is the shortest path from A to B?).

Efficiency is an estimation of the amount of computational resources used by an algorithm. Efficiency is typically expressed as a function of the size of the input.

Formal analysis of algorithms (Big-O) and formal reasoning using mathematical formulas are outside the scope of this course and the AP Exam.

An algorithm’s efficiency is determined through formal or mathematical reasoning.

An algorithm’s efficiency can be informally measured by determining the number of times a statement or group of statements executes.

Different correct algorithms for the same problem can have different efficiencies.

Algorithms with a polynomial efficiency or slower (constant, linear, square, cube, etc.) are said to run in a reasonable amount of time. Algorithms with exponential or factorial efficiencies are examples of algorithms that run in an unreasonable amount of time.

Some problems cannot be solved in a reasonable amount of time because there is no efficient algorithm for solving them. In these cases, approximate solutions are sought.

A heuristic is an approach to a problem that produces a solution that is not guaranteed to be optimal but may be used when techniques that are guaranteed to always find an optimal solution are impractical.

Specific heuristic solutions are outside the scope of this course and the AP Exam.