Glossary
Decision Problems
Problems that have a simple yes or no answer as their output.
Example:
Determining if a student has passed a class (yes/no) based on their grade is a decision problem.
Efficiency
A measure of how many computational resources, such as time or memory, an algorithm consumes relative to the size of its input.
Example:
An algorithm that sorts 100 items in 1 second is more efficient than one that takes 10 seconds for the same task.
Heuristics
Problem-solving techniques that find a good-enough, approximate solution to a problem, especially when finding an exact or optimal solution is too computationally expensive or impossible in a reasonable amount of time.
Example:
When a GPS finds a 'fastest route' that avoids traffic, it often uses heuristics to quickly estimate a good path rather than calculating every single possible route.
Instance
A specific occurrence of a problem with a particular set of inputs.
Example:
If 'sorting a list' is the problem, then sorting the list [5, 2, 8, 1] is an instance of that problem.
Optimization Problems
Problems that aim to find the best possible solution among a set of alternatives, often maximizing or minimizing a value.
Example:
Finding the shortest delivery route for a package to minimize travel time is an optimization problem.
Problem
A task that an algorithm is designed to solve.
Example:
Finding the fastest route to school is a problem that a navigation app's algorithm aims to solve.
Reasonable Time
Refers to algorithms that complete their task in polynomial time or less, meaning their execution time grows proportionally to a polynomial function of the input size, making them practical for large inputs.
Example:
An algorithm that takes N^2 operations to sort N items runs in reasonable time because its growth is polynomial.
Unreasonable Time
Refers to algorithms that complete their task in exponential or factorial time, meaning their execution time grows extremely rapidly with the input size, making them impractical for even moderately large inputs.
Example:
An algorithm that checks every possible combination of items, leading to 2^N operations for N items, runs in unreasonable time.