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.

Definition 3.1.

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.

Remark 3.2.

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.

Assume that . Then the conditions of the definition are fulfilled with the choice , .

Figure 3.1. Figure 1

Example 3.2. Example 2.

Assume that , if . We don' care the relation of the functions for small 's.

Figure 3.2. Figure 2.

Example 3.3. Example 3

Assume , but the function multiplied by a constant is not below .

Figure 3.3. Figure 3

Properties 3.3.

1.  (reflexivity)
2.  for all . 
3. Let  and . Then  (transitivity)

Proof

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. .

Remark 3.4.

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 .

Proof

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

✓

Corollaries 3.6.

1. Let . 
Then  if and only if . 
2. Let . 
Then  if and only if . 
3. Let k > 0. 
Then  and . 
4. Let . 
Then .

Proof

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.

Definition 3.7.

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.

.

The above definition is actually the extension of the usual ones:

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.

Definition 3.8.

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.

Definition 3.9.

Let   be a (monotone increasing) 
function. The set  

is called the class of functions in the order 
of growth of .

Properties 3.10.

1. Let  be two functions. 
Then   if and only if .
2. Let  be two functions. 
Then   if and only if  and 
         

Proof

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 . ✓

Definition 3.11.

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 ".

Properties 3.12.

1. Let  be two function. 
Then  if and oxly if 
. 
2. Let  be a function.
Then  . 
3. Let  be a function.
 Then . 

Proof

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. ✓