AP Computer Science Unit 6

Algorithmic Efficiency

The measure of how effectively an algorithm performs in terms of time and resource usage.

Linear Algorithm

An algorithm that processes data in proportion to the input size, leading to O(n) time complexity.

Quadratic Algorithm

An algorithm that involves nested operations, resulting in O(n²) time complexity.

Constant Time Algorithm

An algorithm that executes a fixed number of steps, regardless of input size, resulting in O(1) time complexity.

Logarithmic Time Algorithm

An algorithm that reduces input size typically by half with each step, resulting in O(log n) time complexity.

Reasonable Time Algorithms

Algorithms such as linear, polynomial, constant, and logarithmic that can execute in a feasible timeframe.

Unreasonable Time Algorithms

Algorithms like exponential and factorial that take significantly longer to execute with increasing input sizes.

Exponential Algorithm

An algorithm that has time complexity represented as O(2^n), which grows rapidly with larger inputs.

Factorial Algorithm

An algorithm with time complexity indicated by n!, showing growth faster than exponential algorithms for larger inputs.

Heuristics

Approaches that provide approximate solutions to problems that are difficult to solve exactly within reasonable time.

Undecidable Problems

Problems that cannot be resolved by any algorithm for all possible inputs due to their fundamental unsolvable nature.

Halting Problem

The problem proven by Alan Turing that states it is impossible to determine whether a program will enter an infinite loop for all inputs.