In latter chapters - in particular at complexity observations - one needs the possibility to express the growth rate order (i.e. the asymptotic behaviour) of functions in a unified way. We define a relation for this, with which one can extract the most important, the steepest growing component of functions.
Let be a monotone increasing function. The set is called the class of functions, in the order of growth of . If , we say that " is a big O " function.
To make the definition clear, the the best if we assume that is a monotone increasing function. However, it is not necessary. If we don't do so, many of the observations would became unexpectedly complicate. Instead of the notation , often the traditional is used.
The most obvious example for the definition if a function bounds an other by above. But this is not necessary to be so. In the following we will demonstrate through some particular example what does the growth rate expresses at first view.
Example 3.1. Example 1.
Example 3.2. Example 2.
Example 3.3. Example 3
1. (reflexivity) 2. for all . 3. Let and . Then (transitivity)
1. Let and . Since for all , thus for all .
2. Let and .Then , i.e. , for all . ✓
3. Let and such that , if and assume that with and the relation holds if . Then with the choice and , we get , if and , i.e. .
1. A transitivity exresses our expectations that if a function grows faster than , then it grows faster than any other, which has slower growth than . 2. The definition of the order of growth rate, can be extended to nonmonotone functions, but this case is not really important for our purposes. 3. The relation of growth rates are neither symmetric, nor antisymmetric. A counterexample for the symmetry ( ) is the pair and , while a counterexample for the antisymmetry ( ) is the pair and .
Further properties 3.5.
4. Let and . Then . 5. Let and . Then . 6. Let be a monotone increasing function, whith and . Then .
3. Assume that with , , and the relations and are true. Let and let . Then .
4. Similarly as before, assume that with , , and the relations and are true. Let and . Then .
5. Assume that and are such that holds. Without loss of generality, we may assume further, that . Since the function is strictly increasing, thus . Since ,thus .
Let . By the monotonicity of we have and
1. Let . Then if and only if . 2. Let . Then if and only if . 3. Let k > 0. Then and . 4. Let . Then .
Corollaries 1, 2, 3 and 4 can be derived from Properties 4, 5 and 6 by simple considerations. ✓
In the following we give the definition of a sequence and a related extremely fast growing function.
Let , be a sequence of functions with the recurrence relation 1. 2. 3.
The first few members of the sequence are the well known mathematical operations.
is the successor,
is the addition, i.e.
is the multiplication, i.e.
is the exponentiation, i.e.
The above definition is actually the extension of the usual ones:
is defined by the consecutive incrementation of by , times;
the multiplication is defined by the consecutive addition of by itself times;
the exponentiation is the consecutive multiplication of by itself times, etc..
With this construction, we obtain a sequence of faster and faster growing functions. By this sequence we can define a function, which grows faster than any of its member:
One can, however, define a function, closely related to the above, without the given sequence.
Ackermann function: Let be a function with the following relation: 1. 2. 3. The function is called the Ackermann function.
The function is approximately the same as (but somewhat less than it). The firs few values of are the following:
|, where k is a number with decimal digits.|
Clearly, this value exceeds all imaginable or even exactly describable limits. (It is much more, than the number atomic particles in the universe, by our best knowledge.) And the function grows faster and faster.
To express the order of growth more precisely, other concepts are used, too. Some of them with results on their properties are given below.
Let be a (monotone increasing) function. The set is called the class of functions in the order of growth of .
1. Let be two functions. Then if and only if . 2. Let be two functions. Then if and only if and
1. Let and such that , for all and let and . Then, by the first inequality,
, for all ha and by the second inequality
, for all . By definition, this is the same as in the statement of the theorem.
2. By the relations and one find that , , and such that , if and , if .
Let and . The two inequalities above implies , if . ✓
Let be a function. The set is called the class of functions with order of growth less than . If , we say that "is a small o ".
1. Let be two function. Then if and oxly if . 2. Let be a function. Then . 3. Let be a function. Then .
1. Let the constants and be such that , if . Then , if , i.e. for arbitrary small there exists a bound such that for all greater thanthe inequality holds. By the definition of limits, this means that . Conversely, means that such that for all . Hence, by a multiplication by we get the statement of our objective.
2. By the definitions, clear that and . Let . Hence, and such that , if and such that if .
Let . With this the inequality holds, for all, which is exactly the statement we wanted to proof.
3. Indirectly, assume that . Then .
With this we find that and such that if and such that , if .
Let . With this we have and , if , which is a contradiction. ✓