4.4.4.1–4.4.4.3 - Functions, growth and algorithm complexity (Java)

Functions and growth rates

A mathematical function maps each permitted input value to exactly one output value, and can describe an operation count for each input size.

In $f:D\to C$, $D$ is the domain, the set of permitted inputs, and $C$ is the co-domain, the specified set from which outputs are drawn. For $f:\mathbb{N}\to\mathbb{N}$, $f(n)=2n$, taking $\mathbb{N}=\{1,2,3,\ldots\}$, every positive integer input maps to an even positive integer. The actual output set (the range) is the even positive integers, although the co-domain also contains odd numbers. A co-domain need not equal the range.

These functions illustrate different growth:

Doubling x doubles $2x$, multiplies $2x^2$ by four and changes $2^x$ much more sharply for large x. A polynomial has fixed powers of the input; in an exponential, the input appears in the exponent. Linear functions are also a special case of polynomials, but algorithm comparisons usually name the linear class separately.

A logarithm is the inverse of exponentiation. $\log_{10}1000=3$ because $10^3=1000$; it is defined for positive inputs. $\log_2 n$ counts how many repeated halvings reduce a power-of-two input size to one. The base changes values by a constant factor and therefore does not change a logarithmic Big-O class.

Permutations and factorials

A permutation is an arrangement of distinct objects in an order, and the number of complete arrangements grows factorially.

For three distinct letters A, B and C, choose the first in three ways, the second from two remaining letters, and the last in one way. This gives ABC, ACB, BAC, BCA, CAB and CBA: six arrangements.

An exhaustive route planner trying every order of n distinct stops has $n!$ candidate orders before counting the work used to score each one. Increasing from five to six stops changes the candidates from 120 to 720, a sixfold increase. This is very different from linear growth. The distinct-object condition matters: repeated identical letters do not produce $n!$ different visible words; this lesson's counting tasks specify distinct objects.

public class Main {
    static long permutations(int n) {
        long result = 1;
        for (int factor = 2; factor <= n; factor++) {
            result *= factor;
        }
        return result;
    }
}

For non-negative n up to 20, this calculation fits Java's signed long. permutations(4) multiplies 1 by 2, 3 and 4 to return 24. The loop computes the number of permutations with linear work; it does not enumerate all 24 arrangements. The complexity of counting a set is not necessarily the complexity of visiting every member.

Time and space complexity

Complexity compares resource requirements as a function of input size, so the size of the problem is the key variable rather than a single observed runtime.

For a list, n is normally its element count; for a graph, vertices and edges may both matter. Define the size measure before comparing algorithms. Time complexity describes growth in work, such as comparisons. Space complexity describes growth in memory. State whether storage includes the input or only additional working storage.