Classification of algorithms revision notes

Comparing algorithms

An algorithm can be compared with another by expressing its complexity as a function of the size of the problem. The size of the problem is the key issue: an algorithm that is suitable for a small input may become unsuitable as the input grows. Efficiency can be considered in terms of time, meaning how the running time grows, and space, meaning how much memory is required. Efficiently implementing an automated abstraction involves designing data models and algorithms that run quickly while using minimal resources such as memory.

Functions and growth

A function maps values from a domain to values in a co-domain, for example ℕ → ℕ. The growth of a function can be linear, polynomial, exponential or logarithmic. Examples include y = 2x, y = 2x², y = 2ˣ and y = log₁₀ x. These different growth rates help describe how an algorithm's requirements change as input size increases.

A permutation is an arrangement of a set of objects or values. For n distinct objects, the number of permutations is n!, where n! is the product of all positive integers less than or equal to n. Factorial growth is an important example of very rapid growth.

Big-O time complexity

Big-O notation expresses how an algorithm's time requirement grows with the size of the problem. The main categories required here are:

• Constant time, O(1): the running-time requirement does not grow with input size.
• Logarithmic time, O(log n): the requirement grows logarithmically as input size increases.
• Linear time, O(n): the requirement grows in proportion to input size.
• Polynomial time, such as O(n²): the requirement grows as a polynomial function of input size.
• Exponential time, such as O(2ⁿ): the requirement grows exponentially with input size.

To derive a time complexity, identify the operation or group of operations whose number of executions depends on n. A fixed number of operations gives O(1). An operation repeated once for each item gives O(n). A nested pair of repetitions, each dependent on n, gives O(n²). The important result is the growth rate as the problem size increases.

Tractable and intractable problems

A problem with a polynomial, or less, time solution is called tractable. A problem with no polynomial, or less, time solution is called intractable. Heuristic methods are often used when tackling intractable problems. Algorithmic complexity and hardware both impose limits on what can be computed in practice.

Computability and the Halting problem

Some problems cannot be solved algorithmically. The Halting problem is the unsolvable problem of determining whether any program will eventually stop when given particular input. It cannot be proved by simply testing enough programs and inputs. Its significance is that it demonstrates that some problems cannot be solved by a computer.

Common errors

Do not confuse time complexity with the exact running time on one machine. Big-O describes growth relative to problem size. Do not assume that every problem is tractable merely because an algorithm exists: tractability concerns whether a polynomial-or-less time solution exists. Also distinguish an intractable problem from a non-computable problem. Intractable problems have no polynomial-or-less solution, whereas some problems cannot be solved algorithmically at all.