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

Functions and growth

A mathematical function maps each input in its domain to exactly one output in its declared co-domain.

For $f:\{1,2,3\}\rightarrow\{1,2,3,4,5,6\}$, defined by $f(x)=2x$, the outputs are 2, 4 and 6. The co-domain contains six values; the range contains three. A function may map different inputs to the same output, but it cannot assign two different outputs to one input. A complexity function can map a problem size $n$ to a count of operations, for example $T:\mathbb{N}\rightarrow\mathbb{N}$, with positive integers used here for problem sizes.

Different families of functions grow at different rates:

A polynomial has fixed nonnegative integer powers such as $3n^3+2n+1$. In an exponential function, the variable is in the exponent: $2^n$ is not $n^2$. Doubling $n$ doubles $2n$ and quadruples $2n^2$, whereas increasing $n$ by one doubles $2^n$. Small input values alone may conceal the eventual difference.

A logarithm is the inverse of exponentiation: $\log_{10}1000=3$ because $10^3=1000$. The logarithmic function has positive real inputs and real outputs, unlike the illustrative integer operation-count mapping. Repeatedly halving a problem explains $\log_2n$ growth: reducing 16 candidates to 1 takes four halvings. Logarithms with different fixed bases differ by a constant factor, which does not change their Big-O class.

Permutations and factorials

A permutation is an ordering of a set of objects, and distinct objects can be ordered in factorially many ways.

For the three distinct letters A, B and C, there are three choices for the first position, two remaining choices for the second and one for the third. The six orders are ABC, ACB, BAC, BCA, CAB and CBA.

Thus $4!=24$, $5!=120$, $6!=720$ and $8!=40320$. Going from $n$ to $n+1$ objects multiplies the number by $n+1$. The empty collection has one empty ordering, so $0!=1$. The formula assumes distinct objects: the word LEVEL has repeated letters, so blindly using $5!$ would count some identical letter strings multiple times.

An exhaustive route planner that considers every ordering of six different delivery stops examines 720 candidates. Checking each candidate's distance requires further work; the candidate count alone is not necessarily the algorithm's complete operation count. Pruning impossible prefixes may improve practical performance, but it does not automatically make the worst case small.

The following C# calculation uses a bounded input so its result fits in long:

static long Factorial(int n) // Precondition: 0 <= n <= 20.
{
    long result = 1;
    for (int factor = 2; factor <= n; factor++)
        result *= factor;
    return result;
}

For n = 4, result becomes 2, 6 and 24. For n = 0 or 1 the loop body is skipped and the method returns 1. The value calculated grows factorially, but the number of loop iterations is $n-1$ for $n\ge2$. Under the ordinary fixed-width arithmetic model, this calculation has linear time. Do not confuse the growth of an output value with the cost of computing it. Unbounded factorials would require larger-number arithmetic and a different model.

Time and space complexity

Complexity compares resource demands as a function of problem size, rather than treating one machine's running time as a universal result.