CHAPTER 3 Functions and Algorithms
3.1Introduction
One of the most important concepts in mathematics is that of a function. The terms “map,” “mapping,”
“transformation,” and many others mean the same thing; the choice of which word to use in a given situation is
usually determined by tradition and the mathematical background of the person using the term.
Related to the notion of a function is that of an algorithm. The notation for presenting an algorithm and a
discussion of its complexity is also covered in this chapter.3.2Functions
Suppose that to each element of a setAwe assign a unique element of a setB; the collection of such
assignments is calleda functionfromAintoB. The setAis called thedomainof the function, and the setBis
called thetarget setorcodomain.
Functions are ordinarily denoted by symbols. For example, letfdenote a function fromAintoB. Then we
write
f:A→B
which is read: “fis a function fromAintoB,” or “ftakes (or maps)AintoB.” Ifa∈A, thenf(a)(read: “fofa”)
denotes the unique element ofBwhichfassigns toa; it is called theimageofaunderf,orthevalueoffata.
The set of all image values is called therangeorimageoff. The image off:A→Bis denoted by Ran(f ),
Im(f )orf(A).
Frequently,a function can be expressed by means of a mathematical formula. For example, consider the
function which sends each real number into its square. We may describe this function by writingf(x)=x^2 or x→x^2 or y=x^2In the first notation,xis called avariableand the letterfdenotes the function. In the second notation, the barred
arrow→is read “goes into.” In the last notation,xis called theindependent variableandyis called thedependent
variablesince the value ofywill depend on the value ofx.
Remark:Whenever a function is given by a formula in terms of a variablex, we assume, unless it is otherwise
stated, that the domain of the function isR(or the largest subset ofRfor which the formula has meaning) and
the codomain isR.43Copyright © 2007, 1997, 1976 by The McGraw-Hill Companies, Inc. Click here for terms of use.