Efficiency of an algorithm (College Board AP® Computer Science Principles): Study Guide
Measuring algorithm efficiency
How is algorithm efficiency measured?
A problem is a general description of a task that can (or cannot) be solved algorithmically
An instance of a problem includes a specific input; for example, sorting is a problem; sorting the list (2, 3, 1, 7) is an instance of that problem
Efficiency is an estimation of the amount of computational resources used by an algorithm, typically expressed as a function of the size of the input
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
Measuring efficiency helps programmers choose the best algorithm for a given task
Types of problems
A decision problem has a yes/no answer, for example, "Is there a path from A to B?"
An optimization problem aims to find the best solution among many options, for example, "What is the shortest path from A to B?"
Reasonable vs unreasonable time
How do we describe whether an algorithm runs quickly enough to be useful?
Algorithms with a polynomial efficiency or lower (constant, linear, square, cube, and so on) are said to run in a reasonable amount of time
Algorithms with exponential or factorial efficiencies run in an unreasonable amount of time, because the number of steps grows too quickly for the algorithm to be practical on large inputs
The distinction between reasonable and unreasonable time is about how efficiency scales with input size, not about whether an algorithm is fast on any single input
Problems that cannot be solved in a reasonable 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 instead of exact ones
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 always find an optimal solution are impractical
For example, a heuristic might follow a simple rule that produces a good-enough solution quickly, instead of exhaustively checking every possibility
Heuristics trade guaranteed optimality for practicality
Examiner Tips and Tricks
When a question asks whether an algorithm runs in a reasonable amount of time, look for how the number of steps grows as the input size grows — not at the number of steps for any single input. Polynomial or lower = reasonable; exponential or factorial = unreasonable.
If a question describes a problem that cannot be solved in a reasonable amount of time and mentions accepting an approximate answer, the concept being tested is heuristics. The AP exam will not ask you to produce or identify a specific heuristic — only to recognize when a heuristic approach is appropriate.
For the AP Create Performance Task, if your program processes a list or dataset, you can discuss in your written response whether your chosen algorithm is efficient for the expected input size, and how its efficiency would change for much larger inputs.
Worked Example
A software team has written two different algorithms that both sort a list of names correctly. Algorithm X has polynomial efficiency; Algorithm Y has exponential efficiency.
For large inputs, which of the following is true?
(A) Algorithm Y runs faster because exponential growth is more efficient than polynomial growth
(B) Algorithm X runs in a reasonable amount of time; Algorithm Y does not
(C) Both algorithms run in a reasonable amount of time because they both solve the problem correctly
(D) Algorithm X runs in an unreasonable amount of time because polynomial growth is slower than exponential growth
[1]
Answer:
(B) Algorithm X runs in a reasonable amount of time; Algorithm Y does not [1 mark]
Algorithms with polynomial efficiency or lower run in a reasonable amount of time; algorithms with exponential or factorial efficiency run in an unreasonable amount of time. Correctness doesn't determine efficiency — both algorithms sort correctly, but Algorithm Y becomes impractical for large inputs because its step count grows too quickly.
Unlock more, it's free!
Join the 100,000+ Students that ❤️ Save My Exams
the (exam) results speak for themselves:
Was this revision note helpful?
