Classification of algorithms key terms

Problem size

The amount of data or work that an algorithm must handle, used as the basis for comparing how its requirements change.

Space efficiency

The extent to which an algorithm minimises the memory and other storage resources needed to operate.

Domain

The set of values supplied as inputs to a function.

Permutation

An arrangement of a set of distinct objects or values; n distinct objects have n! permutations.

Big-O notation

A notation used to describe the growth of an algorithm's running time as the input size increases.

Time complexity

A measure of how the running time requirements of an algorithm grow in relation to the size of its input.

Algorithmic complexity

The way an algorithm's resource requirements, such as processing time or memory, change as the input size increases.

Hardware limit

A restriction caused by the finite processing speed or memory available in a computer system.

Tractable

Describes a problem that has a polynomial (or less) time solution.

Intractable

Describes a problem that has no polynomial (or less) time solution.

Computable problem

A problem for which an algorithm exists that can solve it.

Non-computable problem

A problem that cannot be solved algorithmically in every case.

Halting

The eventual stopping of a program.

Unsolvable problem

A problem that cannot be solved by a computer in all possible cases.