4.4.4.1–4.4.4.3 - Functions, growth and algorithm complexity (VB.NET)

Functions and growth

A mathematical function maps each value in its domain to exactly one value in its co-domain. The domain is the set of permitted inputs; the co-domain is the declared set from which outputs are drawn. The range is the set of outputs actually reached, which may be a smaller set.

For example, $f:\mathbb{N}_0\rightarrow\mathbb{N}_0$, $f(n)=2n$, maps non-negative integers to non-negative integers. Its range contains only the even non-negative integers. A mathematical function is a mapping, not necessarily a VB.NET Function declaration; code can implement the mapping when its types and bounds permit.

Different functions grow very differently. For the following numerical examples use positive real x, allowing $\log_{10}x$ to have real outputs:

An exponential has the variable in the exponent; a quadratic has the variable as the base of a fixed power. $2x^2$ and $2^x$ are therefore different growth rules. A logarithm answers an exponent question: $\log_{10}1000=3$ because $10^3=1000$. It is defined here only for positive inputs.

[DIAGRAM: asset_slug: vbnet_growth_functions; description: Four exact growth functions on x from 1 to 10, with separate labelled vertical scales.]

The separate vertical scales make each shape readable; compare the formula and the labelled values, not the panel heights. For algorithm analysis, n usually counts discrete input items. Mathematical growth helps predict what increasing n does to the required work, without assuming every algorithm has the same cost per operation.

Permutations and factorials

A permutation is an arrangement of objects in an order. With n distinct objects there are n choices for the first position, n−1 for the second and so on, giving n factorial arrangements.

For A, B and C, the six permutations are ABC, ACB, BAC, BCA, CAB and CBA: $3!=3\times2\times1=6$. Four distinct items have $4!=24$ arrangements; adding a fifth multiplies that by five to give 120. Distinctness matters: swapping indistinguishable repeated letters does not create a new visible arrangement, so blindly using n! would overcount repeated-letter words.

An algorithm checking every order of eight distinct visits has $8!=40320$ candidates, compared with only $4!=24$ for four visits. Counting candidates reveals why exhaustive checking can become impractical even if checking one candidate is quick. The count of candidates is not necessarily the complete work: if each candidate also needs n checks, include that work in the analysis. For the empty arrangement convention, $0!=1$, because there is one way to arrange no objects.

Time and space requirements

Time complexity describes how required work grows with problem size. Space complexity describes how required memory grows. Size is central: a method that is quick for ten items may be unsuitable for ten million.