📚

All Subjects

 > 

⌨️ 

AP Comp Sci P

 > 

📱

Big Idea 3: Algorithms and Programming

3.17 Algorithmic Efficiency

2 min read•november 16, 2020

minnachow

Minna Chow


AP Computer Science Principles ⌨️

Bookmarked 2.3k • 69 resources
See Units

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.
https://firebasestorage.googleapis.com/v0/b/fiveable-92889.appspot.com/o/images%2F-Sh0mIlTWmXUS.gif?alt=media&token=502e3e52-249f-4c2a-8ecb-b585adc784b9

It's more optimal for a computer to find the best route than it is for you to attempt it with a map. Image source: Moonrise Kingdom/GIPHY

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.

Was this guide helpful?

Join us on Discord
Thousands of students are studying with us for the AP Computer Science Principles exam.
join now
Hours Logo
Studying with Hours = the ultimate focus mode
Start a free study session
🔍 Are you ready for college apps?
Take this quiz and find out!
Start Quiz
Browse Study Guides By Unit
Join us on Discord
Thousands of students are studying with us for the AP Computer Science Principles exam.
join now
💪🏽 Are you ready for the AP CSP exam?
Take this quiz for a progress check on what you’ve learned this year and get a personalized study plan to grab that 5!
START QUIZ