AP Computer Science Principles Flashcards: Algorithmic Efficiency
Written by AP Content Team, Verified for 2026 AP Exams, Last updated: May 2026
Review key ideas with interactive flashcards. This set includes 24 cards to help you master important concepts.
What is an informal way to measure an algorithm's efficiency?
Efficiency can be informally measured by determining the number of times a statement or group of statements executes as the input size grows.
Card 1 of 24
All Flashcards (24)
What is an informal way to measure an algorithm's efficiency?
Efficiency can be informally measured by determining the number of times a statement or group of statements executes as the input size grows.
What is an 'instance' of a problem?
An instance of a problem is the general task description along with specific input.
Can two different, correct algorithms for the same problem have different efficiencies?
Yes, different correct algorithms designed to solve the same problem can have significantly different efficiencies.
An algorithm's efficiency is determined to be factorial. Is this considered reasonable or unreasonable?
This is considered unreasonable time, as factorial efficiency grows extremely quickly and is impractical for even moderately sized inputs.
What is a 'problem' in an algorithmic context?
A problem is a general description of a task that can or cannot be solved algorithmically.
What is the difference between algorithms that run in 'reasonable' vs. 'unreasonable' time?
Algorithms with polynomial efficiency or lower run in reasonable time, while those with exponential or factorial efficiencies run in unreasonable time.
Define an 'optimization problem'.
An optimization problem is a problem that seeks to find the 'best' possible solution among many options.
What is the primary difference between a decision problem and an optimization problem?
A decision problem requires a simple yes/no answer, whereas an optimization problem requires finding the best solution from a set of possibilities.
What does it mean for efficiency to be 'a function of the size of the input'?
It means that the amount of resources an algorithm uses (its efficiency) is expected to change as the size of the input data changes.
Why are approximate solutions sometimes necessary?
Approximate solutions are sought when a problem cannot be solved in a reasonable amount of time because no efficient algorithm exists for it.
An algorithm's efficiency is determined to be linear. Is this considered reasonable or unreasonable?
This is considered reasonable time, as linear efficiency is a type of polynomial efficiency.
How is an algorithm's efficiency formally determined?
An algorithm's efficiency is determined through formal or mathematical reasoning, not just by running the code and timing it.
When is it appropriate to use a heuristic solution?
A heuristic is appropriate when an exact, optimal solution is impractical to find because the known algorithms run in an unreasonable amount of time.
A problem asks: 'Is there a path from point A to point B under 10 miles?' What type of problem is this?
This is a decision problem because the answer will be a simple 'yes' or 'no'.
Define a 'decision problem'.
A decision problem is a problem that has a yes or no answer.
An algorithm has a cubic efficiency. Is its runtime considered reasonable or unreasonable?
Its runtime is considered reasonable. Cubic efficiency is a type of polynomial efficiency, which falls into the category of reasonable time.
Why can't some problems be solved in a reasonable amount of time?
Some problems cannot be solved in a reasonable amount of time because no efficient (polynomial or lower) algorithm has been discovered for them.
Is a solution found using a heuristic approach guaranteed to be the best one?
No, a heuristic produces a solution that is not guaranteed to be optimal, but it is often sufficient and can be found quickly.
A problem asks: 'What is the shortest path from point A to point B?' What type of problem is this?
This is an optimization problem because it seeks the 'best' (shortest) solution among all possible paths.
If the only known algorithm to solve a problem has an exponential run time, what approach might a programmer use to get a usable answer?
The programmer might use a heuristic to find an approximate solution, as the optimal algorithm is too inefficient to be practical.
What types of algorithm efficiencies are considered to run in a 'reasonable amount of time'?
Algorithms with a polynomial efficiency or lower (e.g., constant, linear, square, cube) are considered to run in a reasonable amount of time.
What is algorithmic 'efficiency'?
Efficiency is an estimation of the computational resources (like time or memory) used by an algorithm, expressed as a function of the input size.
What are two examples of algorithm efficiencies that are considered 'unreasonable'?
Algorithms with exponential or factorial efficiencies are examples of algorithms that run in an unreasonable amount of time.
What is a 'heuristic'?
A heuristic is an approach that produces a solution that is not guaranteed to be optimal but is used when optimal techniques are impractical.