Fiveable
Fiveable

or

Log in

Find what you need to study


Light

Find what you need to study

3.17 Algorithmic Efficiency

2 min readjanuary 12, 2023

Minna Chow

Minna Chow

Milo Chang

Milo Chang

Minna Chow

Minna Chow

Milo Chang

Milo Chang

Problems

Generally speaking, a problem is a task that an is trying to solve. An of the problem is a problem with a specific input. The example the College Board CED gives is that is a problem while the list [2, 3, 1, 7] is an 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 , because you can answer that question with a yes or a no. Finding the between two cities, on the other hand, is considered an . 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

Efficiency

An 's efficiency is an estimate of how many (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 —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 . The technique to find this is known as a heuristic.

Key Terms to Review (13)

Algorithm

: An algorithm is a step-by-step procedure or set of rules for solving a specific problem or accomplishing a task within a finite number of steps.

Approximate Solution

: An approximate solution is a solution that is not exact or precise, but rather an estimation or close enough answer to a problem. It provides a reasonable and practical result without the need for complete accuracy.

Computational Resources

: Computational resources refer to the hardware and software components necessary for performing computations or running programs.

Decision Problem

: A decision problem is a computational problem that requires a yes or no answer, such as determining whether a given number is prime.

Exponential Efficiency

: Exponential efficiency refers to an algorithm or function whose running time grows exponentially with respect to its input size. In other words, as the input gets larger, this type of algorithm experiences rapid growth in its execution time.

Factorial Efficiency

: Factorial efficiency refers to an algorithm or function whose running time grows factorially with respect to its input size. In other words, as the input gets larger, this type of algorithm experiences extremely rapid growth in its execution time.

Input Size

: Input size refers to the amount of data provided as input to an algorithm or program.

Instance

: An instance refers to each individual occurrence or example within a larger set or class.

Optimization Problem

: An optimization problem involves finding the best solution among many possible solutions, often by maximizing or minimizing an objective function.

Polynomial Efficiency

: Polynomial efficiency refers to an algorithm or function that has a time complexity that can be represented by a polynomial equation. This means that the running time of the algorithm grows at a rate proportional to some power of the input size.

Prime Number

: A prime number is any positive integer greater than 1 that has no divisors other than 1 and itself.

Shortest Path

: The shortest path refers to the route with the minimum total distance between two points in a graph or network.

Sorting

: Sorting refers to arranging elements in ascending or descending order based on certain criteria, such as numerical value or alphabetical order.

3.17 Algorithmic Efficiency

2 min readjanuary 12, 2023

Minna Chow

Minna Chow

Milo Chang

Milo Chang

Minna Chow

Minna Chow

Milo Chang

Milo Chang

Problems

Generally speaking, a problem is a task that an is trying to solve. An of the problem is a problem with a specific input. The example the College Board CED gives is that is a problem while the list [2, 3, 1, 7] is an 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 , because you can answer that question with a yes or a no. Finding the between two cities, on the other hand, is considered an . 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

Efficiency

An 's efficiency is an estimate of how many (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 —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 . The technique to find this is known as a heuristic.

Key Terms to Review (13)

Algorithm

: An algorithm is a step-by-step procedure or set of rules for solving a specific problem or accomplishing a task within a finite number of steps.

Approximate Solution

: An approximate solution is a solution that is not exact or precise, but rather an estimation or close enough answer to a problem. It provides a reasonable and practical result without the need for complete accuracy.

Computational Resources

: Computational resources refer to the hardware and software components necessary for performing computations or running programs.

Decision Problem

: A decision problem is a computational problem that requires a yes or no answer, such as determining whether a given number is prime.

Exponential Efficiency

: Exponential efficiency refers to an algorithm or function whose running time grows exponentially with respect to its input size. In other words, as the input gets larger, this type of algorithm experiences rapid growth in its execution time.

Factorial Efficiency

: Factorial efficiency refers to an algorithm or function whose running time grows factorially with respect to its input size. In other words, as the input gets larger, this type of algorithm experiences extremely rapid growth in its execution time.

Input Size

: Input size refers to the amount of data provided as input to an algorithm or program.

Instance

: An instance refers to each individual occurrence or example within a larger set or class.

Optimization Problem

: An optimization problem involves finding the best solution among many possible solutions, often by maximizing or minimizing an objective function.

Polynomial Efficiency

: Polynomial efficiency refers to an algorithm or function that has a time complexity that can be represented by a polynomial equation. This means that the running time of the algorithm grows at a rate proportional to some power of the input size.

Prime Number

: A prime number is any positive integer greater than 1 that has no divisors other than 1 and itself.

Shortest Path

: The shortest path refers to the route with the minimum total distance between two points in a graph or network.

Sorting

: Sorting refers to arranging elements in ascending or descending order based on certain criteria, such as numerical value or alphabetical order.


© 2024 Fiveable Inc. All rights reserved.

AP® and SAT® are trademarks registered by the College Board, which is not affiliated with, and does not endorse this website.


© 2024 Fiveable Inc. All rights reserved.

AP® and SAT® are trademarks registered by the College Board, which is not affiliated with, and does not endorse this website.