AP CSP
AP Computer Science Principles / All lessons / Big Idea 3: Algorithms and Programming
3Big Idea 3: Algorithms and Programming
AP CSP topic 3.17

Algorithmic Efficiency

Efficiency describes how much time or memory an algorithm needs as the input size grows. Algorithms that grow at a polynomial rate, like n or n squared steps, run in a reasonable time. Algorithms that grow exponentially, like 2 to the n, quickly become impossible to run for large inputs. For some hard problems, programmers use a heuristic: an approach that finds a good-enough answer quickly instead of the perfect one.

Picture it n n² 2ⁿ input size n →steps →
How the number of steps grows as the input n grows. Reasonable time: n and n². Unreasonable time: 2ⁿ shoots up so fast that big inputs are impossible.

Algorithmic Efficiency vocabulary

  • Efficiency: The amount of computing resources an algorithm uses relative to input size.
  • Reasonable time: Running time that grows at a polynomial rate or slower.
  • Unreasonable time: Running time that grows exponentially or faster.
  • Heuristic: A shortcut that gives a good-enough solution when the best one takes too long.

AP-style practice questions

Try each one, then open the answer. To save your progress, take this quiz in the interactive course.

Skill: Algorithms and Program Development 
Algorithm P takes n² steps for a list of n elements.
Algorithm Q takes 2ⁿ steps for a list of n elements.

1. Which of the following is true for large lists?

  1. (A) Both run in a reasonable amount of time
  2. (B) P runs in a reasonable time, but Q does not
  3. (C) Q runs in a reasonable time, but P does not
  4. (D) Neither runs in a reasonable time
Show answer

(B) P runs in a reasonable time, but Q does not Polynomial growth (n²) is reasonable. Exponential growth (2ⁿ) is not.

Skill: Algorithms and Program Development

2. Finding the shortest route through 60 cities by checking every possible order would take far too long. Which approach is most practical?

  1. (A) Check every route anyway
  2. (B) Use a heuristic that finds a good route quickly, even if not the best
  3. (C) Give up because the problem is undecidable
  4. (D) Use a smaller computer
Show answer

(B) Use a heuristic that finds a good route quickly, even if not the best Heuristics trade a perfect answer for a good one found in reasonable time.

Skill: Code Analysis

3. A linear search checks each element of a list once. If the list doubles in size, about how does the worst-case number of checks change?

  1. (A) It stays the same
  2. (B) It doubles
  3. (C) It squares
  4. (D) It is cut in half
Show answer

(B) It doubles Linear search grows in direct proportion to the number of elements.

Skill: Algorithms and Program Development

4. Which of the following best describes algorithmic efficiency?

  1. (A) How many lines of code an algorithm has
  2. (B) How much time or memory an algorithm uses as the input size grows
  3. (C) Whether the algorithm has comments
  4. (D) How fast the programmer typed it
Show answer

(B) How much time or memory an algorithm uses as the input size grows Efficiency compares resource use to input size.

Open 3.17 in the interactive course