## Chapter 3. Order of growth rate

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

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

Example 3.2. Example 2.

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

Example 3.3. Example 3

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

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.

1. is the successor,

3. is the multiplication, i.e.

4. is the exponentiation, i.e.

.

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

1. is defined by the consecutive incrementation of by , times;

2. the multiplication is defined by the consecutive addition of by itself times;

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

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