๐Ÿ“š

All Subjects

ย >ย 

โŒจ๏ธย 

AP Comp Sci P

ย >ย 

๐Ÿ“ฑ

Big Idea 3: Algorithms and Programming

Algorithmic Efficiency

2 min readโ€ขoctober 12, 2021

minnachow

Minna Chow


AP Computer Science Principlesย โŒจ๏ธ

Bookmarkedย 2.6kย โ€ขย 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?

Fiveable logo
Join Fiveable for free
Create a free account to bookmark content and compete in trivia
Hours Logo
Studying with Hours = the ultimate focus mode
Start a free study session
Browse Study Guides By Unit
๐Ÿ•นBig Idea 1: Creative Development
โš™๏ธBig Idea 2: Data
๐Ÿ“ฑBig Idea 3: Algorithms and Programming
๐Ÿ–ฅBig Idea 4: Computer Systems and Networks
โŒจ๏ธBig Idea 5: Impact of Computing
โœ๏ธFrequently Asked Questions
๐Ÿ“Exam Prep
๐Ÿ“ฑ Stressed or struggling and need to talk to someone?
Talk to a trained counselor for free. It's 100% anonymous.
Text FIVEABLE to 741741 to get started.
ยฉ 2021 Fiveable, Inc.