2 min readβ’january 13, 2023

Minna Chow

Milo Chang

Generally speaking, a **problem** is a task that an algorithm is trying to solve**. **An** instance **of the problem is a problem with a *specific input***. **The example the College Board CED gives is that sorting is a problem while sorting the list [2, 3, 1, 7] is an instance of the problem.

Some examples of common problem types are** decision problems **and** optimization problems.** Decision problems have a yes/no answer, while optimization problems ask what the best solution is to the task at hand.

Finding out if a number is prime is a decision problem, because you can answer that question with a yes or a no. Finding the shortest path between two cities, on the other hand, is considered an optimization problem. It wants the *best* answer (in this case the shortest), not just an answer.

An algorithm's **efficiency **is an estimate of how many computational resources (like power, memory or time) it uses. It's officially expressed as a function of the size of the input. This just means that the efficiency varies based on the input sizeβthe bigger the input, the more resources it'll use, and vice versa. There are formal equations to calculate it, but you don't have to know them for the AP CSP test.

Informally, efficiency is measured by determining how many times a statement or statement group executes. Algorithms that run with a *polynomial *efficiency or lower are said to run in a** reasonable** amount of time while algorithms that run with an *exponential* or *factorial *efficiency run in an **unreasonable **amount of time.

Different correct algorithms for the same problem can have different efficiencies, just like how different ways to solve a problem can take longer or shorter or be more or less effective.

Some problems can't be solved in a reasonable amount of time. In this case, computers turn to an approximate solution. The technique to find this approximate solution is known as a** heuristic. **

Browse Study Guides By Unit

πΉUnit 1 β Creative Development

βοΈUnit 2 β Data

π±Unit 3 β Algorithms & Programming

π₯Unit 4 β Computer Systems & Networks

β¨οΈUnit 5 β Impact of Computing

βοΈFrequently Asked Questions

πExam Prep

Β© 2023 Fiveable Inc. All rights reserved.