3.17 Algorithmic Efficiency
⌨️AP Computer Science Principles Unit 3 Review
3.17 Algorithmic Efficiency
⌨️ AP Computer Science Principles
Big Idea 3: Algorithms and Programming
3.1
Variables and Assignments
3.2
Data Abstraction
3.3
Mathematical Expressions
3.4
Strings
3.5
Boolean Expressions
3.6
Conditionals
3.7
Nested Conditionals
3.8
Iteration
3.9
Developing Algorithms
3.10
Lists
3.11
Binary Search
3.12
Calling Procedures
3.13
Developing Procedures
3.14
Libraries
3.15
Random Values
3.16
Simulations
3.17
Algorithmic Efficiency
3.18
Undecidable Problems
TLDR
Algorithmic efficiency is about how many computational resources an algorithm uses as the input gets bigger. For AP Computer Science Principles, you need to tell the difference between algorithms that run in a reasonable amount of time (polynomial or lower) and those that run in an unreasonable amount of time (exponential or factorial), and know that a heuristic gives a good-enough answer when finding the perfect one would take too long.
Algorithmic efficiency is an estimate of how many computational resources an algorithm uses as its input grows, and it falls under Algorithms and Programming, the largest part of the multiple-choice section.
Efficiency Measures Resource Use as Input Grows
- A problem is a general task (like sorting); an instance of a problem is that task with specific input (like sorting [2, 3, 1, 7]).
- Decision problems have yes/no answers; optimization problems ask for the best solution among many.
- Efficiency estimates the computational resources an algorithm uses and is expressed in terms of input size.
- Informally, you measure efficiency by counting how many times a statement or group of statements runs.
- Polynomial efficiency or lower runs in a reasonable amount of time; exponential or factorial efficiency runs in an unreasonable amount of time.
- A heuristic gives a solution that is not guaranteed to be optimal but is useful when the exact method is impractical.
Problems and Instances
A problem is a general description of a task that an algorithm tries to solve. An instance of a problem is that same task with a specific input. For example, sorting is the problem, while putting the list [2, 3, 1, 7] in order is one instance of it.
Two common categories of problems:
- Decision problems have a yes or no answer. Checking whether a number is prime is a decision problem because the answer is yes or no.
- Optimization problems ask for the best solution among many options. Finding the shortest path between two cities is an optimization problem because you want the best answer, not just any answer.
Efficiency
An algorithm's efficiency is an estimate of how many computational resources it uses, such as time or memory. You usually describe efficiency as a function of input size, which just means that a bigger input tends to make the algorithm need more resources.
You do not need formal analysis or Big-O notation for AP Computer Science Principles. Instead, you can measure efficiency informally by counting how many times a statement or group of statements executes as the input grows.
A key idea: different correct algorithms for the same problem can have different efficiencies. Two algorithms might both give the right answer, but one could finish much faster than the other.
Reasonable vs Unreasonable Time
Efficiency is often described by how it scales with input size:
- Reasonable time: algorithms with polynomial efficiency or lower (constant, linear, square, cube, and so on).
- Unreasonable time: algorithms with exponential or factorial efficiency.
As the input gets large, an unreasonable-time algorithm can take so long that it becomes impractical to run, even for a fast computer.
Heuristics
For some problems, no efficient algorithm exists, so they can't be solved within a reasonable time. When the exact method that guarantees the best answer is impractical, programmers look for an approximate solution.
A heuristic is an approach that gives a solution that may not be the optimal one but is good enough to be useful. You give up the guarantee of the perfect answer in exchange for an answer you can actually get in a reasonable amount of time. (Specific heuristic methods are outside the scope of the exam, so focus on what a heuristic is and when one makes sense to use.)
Comparing Algorithms by Counting Statement Executions
MCQ:
- When a question gives you two correct algorithms, do not just check that they work. Compare how many times their key statements run as the input grows, then pick the more efficient one.
- Watch for the words "reasonable" and "unreasonable." Match polynomial or lower to reasonable, and exponential or factorial to unreasonable.
- If a question describes a problem that gets huge as input grows and asks for a practical approach, think heuristic.
Problem Solving:
- To estimate efficiency, count statement executions. A loop that runs once per item suggests it scales with input size; a loop inside a loop suggests it scales faster.
- Sort problem descriptions into decision (yes/no) or optimization (best of many) before answering.
Common Trap:
- Faster and more efficient are not the same as "correct." A less efficient algorithm can still produce the right output.
Common Misconceptions
- Misconception: Efficiency is the same as correctness.Actually: Efficiency is not the same as correctness. Two algorithms can both be correct and still have very different efficiencies.
- Misconception: You need Big-O or efficiency formulas.Actually: You do not need Big-O or efficiency formulas. This topic uses informal reasoning about how many times statements run, not formal math proofs.
- Misconception: Unreasonable time means impossible.Actually: Unreasonable time does not mean impossible. An exponential or factorial algorithm may still produce an answer; it just may take far too long to be practical as the input grows.
- Misconception: A heuristic gives the guaranteed best answer.Actually: A heuristic does not give the guaranteed best answer. It gives a useful, good-enough solution when finding the optimal one is impractical.
- Misconception: A problem and an instance are the same.Actually: A problem and an instance are different. A problem is the general task; an instance includes specific input.
Related AP Computer Science Principles Guides
Practice Questions for 3.17
1 of 10
The flowchart above represents an algorithm for a computer opponent in a board game. During testing, the programmer discovers that the algorithm works quickly for the first few turns, but later in the game, it appears to freeze and takes hours to choose a single move.
Which option best identifies the cause of this error and a valid fix?
A.
The algorithm has reasonable time but uses too much memory; store states in one list.
B.
The algorithm has unreasonable time because states grow exponentially; use a heuristic.
C.
The algorithm has reasonable time but enters an infinite loop; add a stop condition.
D.
The algorithm has unreasonable time because states grow polynomially; evaluate all moves in constant time.
Vocabulary
The following words are mentioned explicitly in the AP® course framework for this topic.Term | Definition |
|---|---|
algorithm | Step-by-step procedures or sets of rules designed to solve a problem or accomplish a task. |
approximate solution | A solution that is not guaranteed to be optimal but is sought when efficient algorithms for finding optimal solutions are impractical. |
decision problem | A problem that requires a yes-or-no answer as output. |
efficiency | An estimation of the amount of computational resources (such as time or memory) used by an algorithm, typically expressed as a function of the input size. |
exponential efficiency | An algorithm's efficiency that grows exponentially with input size, causing it to run in an unreasonable amount of time. |
factorial efficiency | An algorithm's efficiency that grows at a factorial rate with input size, causing it to run in an unreasonable amount of time. |
heuristic | 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. |
optimization problem | A problem with the goal of finding the best solution among many possible solutions. |
polynomial efficiency | An algorithm's efficiency that grows at a polynomial rate (constant, linear, square, cube, etc.) relative to input size, allowing it to run in reasonable time. |
problem | A general description of a task that can or cannot be solved algorithmically, which may have specific inputs or instances. |
reasonable time | Algorithms with polynomial efficiency or lower (constant, linear, square, cube, etc.) that can be solved in a practical amount of time. |
unreasonable time | Algorithms with exponential or factorial efficiencies that require impractically long amounts of time to solve. |
See Fiveable more often in Google
Mark Fiveable as a preferred source and Google is more likely to show you our guides in Top Stories, with a "preferred" badge in AI Mode and AI Overviews.