Summary
The subject of this lecture is the concept of function. In principle,
function is a special kind of relation between the elements of two
sets. Mapping of the type:
student →
his index number
book title → its author
are examples of functions. Functions will be present in all
lectures of this course. In this lecture we will introduce the concept
itself, and its properties. We will introduce operations on functions
that are similar to that defined for relations. We will also discuss
sequences as a special type of functions. Finally, we will present the
idea of order of function, which will allow us to compare the rate of
increase in different functions. This concept is very useful when
determining the costs of algorithms and programs.
The idea of function is quite abstract and, therefore, difficult to
comprehend. Understanding it and understanding the difference between
the relation and function are the main benefits the student should gain
from
this lecture.
It seems, that the good method of assimilating the contained here
information is checking independently the given lemma and
comparing results with the one provided. We pass without proof the part
of
statements so as not to bore the Readers with a large number of
detailed
arguments. All proofs which were skipped here can be found in the
recommended literature.
Asymptotic notation, discussed in the last section of the
lecture, though very important in computer science, can be postponed
for a
moment. We will come back to this notion in different points of
this lecture and, when necessary, the Reader can return to this
part of the lecture.