AP Computer Science Principles Practice Quiz: Algorithmic Efficiency

Written by AP Content Team, Verified for 2026 AP Exams, Last updated: May 2026

Test your understanding with short quizzes. This quiz has 16 questions to check your progress.

Question 1 of 16

An algorithm's efficiency is determined to be polynomial. According to the provided text, what can be concluded about its runtime?

A)It runs in a reasonable amount of time.B)It runs in an unreasonable amount of time.C)It will produce an approximate, but not optimal, solution.D)It is a decision problem.

All Questions (16)

An algorithm's efficiency is determined to be polynomial. According to the provided text, what can be concluded about its runtime?

A) It runs in a reasonable amount of time.

B) It runs in an unreasonable amount of time.

C) It will produce an approximate, but not optimal, solution.

D) It is a decision problem.

Correct Answer: A

The provided content states that 'Algorithms with a polynomial efficiency or lower (constant, linear, square, cube, etc.) run in a reasonable amount of time.'

Under which circumstance is a heuristic approach most appropriate for solving a problem?

A) When the problem is a simple decision problem with a yes/no answer.

B) When multiple correct algorithms exist, and the most efficient one needs to be chosen.

C) When finding a guaranteed optimal solution is computationally impractical.

D) When the efficiency must be determined through formal mathematical reasoning.

Correct Answer: C

A heuristic is used 'when optimal techniques are impractical' and provides a solution that is 'not guaranteed to be optimal.' This is often the case for problems that cannot be solved in a reasonable amount of time.

Consider the task of sorting a list of numbers. Which of the following is an *instance* of this problem?

A) The general description of arranging numbers in ascending order.

B) An algorithm like Bubble Sort or Merge Sort.

C) The question 'Is this list of numbers sorted?'

D) The specific list [5, 2, 8, 1, 9] that needs to be sorted.

Correct Answer: D

A problem is a 'general description of a task,' while an instance of a problem 'also includes specific input.' Sorting is the general problem; the list [5, 2, 8, 1, 9] is the specific input, making it an instance.

A programmer is tasked with creating a program that determines if a path exists between two nodes in a graph. What type of problem is this?

A) An optimization problem

B) A decision problem

C) A heuristic problem

D) An unreasonable problem

Correct Answer: B

The problem requires a 'yes/no answer' (Does a path exist?), which is the definition of a decision problem.

What does the efficiency of an algorithm primarily estimate?

A) The correctness of the algorithm's output.

B) The amount of computational resources used relative to input size.

C) The number of programmers required to write the algorithm.

D) The programming language used to implement the algorithm.

Correct Answer: B

The text defines efficiency as 'an estimation of the amount of computational resources used by an algorithm, typically expressed as a function of the size of the input.'

Some problems, like the Traveling Salesperson Problem, cannot be solved optimally in a reasonable amount of time for large inputs. What is a common strategy for finding a workable solution to such problems?

A) Proving through mathematical reasoning that no solution exists.

B) Applying a heuristic to find an approximate, good-enough solution.

C) Breaking the problem down into smaller decision problems.

D) Running the algorithm on a more powerful computer until the optimal solution is found.

Correct Answer: B

The text states that for problems that 'cannot be solved in a reasonable amount of time... approximate solutions are sought.' It then defines a heuristic as an approach that provides such a solution when optimal techniques are impractical.

Two different algorithms are created to solve the exact same problem. Both algorithms are proven to be correct. Which of the following statements must be true?

A) Both algorithms must have the same efficiency.

B) The algorithms could have different efficiencies.

C) One algorithm must be an optimization and the other a decision algorithm.

D) The algorithm with fewer lines of code is always more efficient.

Correct Answer: B

The provided content explicitly states, 'Different correct algorithms for the same problem can have different efficiencies.'

Which of the following efficiency classes is considered to run in an 'unreasonable' amount of time?

A) Constant

B) Linear

C) Square (Quadratic)

D) Exponential

Correct Answer: D

The text identifies 'Algorithms with exponential or factorial efficiencies' as examples of algorithms that run in an unreasonable amount of time.

A student is analyzing a simple sorting algorithm. To informally measure its efficiency, they count the number of times the comparison `if (list[j] > list[j+1])` is executed within the loops. This approach aligns with which concept?

A) An algorithm's efficiency can be informally measured by counting statement executions.

B) An algorithm's efficiency is determined solely through formal mathematical reasoning.

C) This is an example of using a heuristic to find an approximate solution.

D) This method only works for algorithms with linear efficiency.

Correct Answer: A

The text states, 'An algorithm’s efficiency can be informally measured by determining the number of times a statement or group of statements executes.' The student's action is a direct application of this principle.

A GPS application needs to calculate the route with the shortest travel time from a starting point to a destination, considering all possible routes. This is an example of:

A) A decision problem

B) An optimization problem

C) A problem instance

D) An unreasonable time problem

Correct Answer: B

The problem 'seeks the 'best' solution among many' (the shortest route), which is the definition of an optimization problem.

A computer scientist analyzes an algorithm and proves that its runtime grows as a function of the square of the input size (n²). What does this analysis represent?

A) An informal measurement based on counting statement executions.

B) A heuristic approach to finding an approximate solution.

C) A determination of efficiency through formal or mathematical reasoning.

D) A conclusion that the algorithm runs in an unreasonable amount of time.

Correct Answer: C

Describing the runtime as a mathematical function of the input size (n²) is a form of formal analysis. The text states, 'An algorithm’s efficiency is determined through formal or mathematical reasoning.' A square (polynomial) efficiency is considered reasonable.

What is the primary trade-off when using a heuristic?

A) Sacrificing correctness for faster runtime.

B) Sacrificing a guaranteed optimal solution for a practical, timely one.

C) Sacrificing reasonable runtime for a guaranteed optimal solution.

D) Sacrificing a simple solution for a more complex but efficient one.

Correct Answer: B

A heuristic 'produces a solution not guaranteed to be optimal' but is used when finding the optimal solution is 'impractical.' This describes a trade-off between optimality and practicality/speed.

According to the provided text, what is a 'problem' in the context of computer science?

A) A specific set of inputs for an algorithm.

B) A bug or error in a program's code.

C) A general description of a task to be solved algorithmically.

D) An algorithm that runs in an unreasonable amount of time.

Correct Answer: C

The text defines a problem as 'a general description of a task that can (or cannot) be solved algorithmically.'

A developer has four algorithms to solve a problem, with the following efficiencies. Which algorithm runs in a reasonable amount of time?

A) Factorial

B) Exponential

C) Linear

D) An algorithm for which no efficient solution is known.

Correct Answer: C

The text specifies that algorithms with polynomial efficiency or lower, which includes constant, linear, square, and cube, 'run in a reasonable amount of time.' Factorial and exponential are unreasonable.

An algorithm is designed to find the absolute best way to pack boxes into a truck. It has an exponential efficiency. Which of the following statements is the most accurate description of this situation?

A) This is a decision problem that runs in a reasonable amount of time.

B) This is an optimization problem that runs in an unreasonable amount of time.

C) This is a decision problem that runs in an unreasonable amount of time.

D) This is an optimization problem that runs in a reasonable amount of time.

Correct Answer: B

The problem seeks the 'best' solution, making it an optimization problem. The exponential efficiency means it runs in an unreasonable amount of time for non-trivial inputs.

An algorithm's efficiency is often described as O(n), O(n²), or O(2ⁿ). What does the 'n' in these expressions typically represent?

A) The number of lines of code in the algorithm.

B) The number of times a statement executes, regardless of input.

C) The size of the input to the algorithm.

D) The number of possible solutions to the problem.

Correct Answer: C

The text states that efficiency is 'typically expressed as a function of the size of the input.' The variable 'n' is the standard representation for the size of the input.