412
Relations, Functions, and Matrices
Exercises 77 and 78 involve programming with a functional language. Functional programming languages, as
opposed to conventional (procedural) programming languages such as C++, Java, or Python, treat tasks in
terms of mathematical functions. A mathematical function such as f (x) = 2x transforms the argument 5 into
the result 10. Think of a program as a big function to transform input into output. A functional programming
language contains primitive functions as part of the language, and the programmer can define new functions as
well. Functional programming languages support function composition, allowing for complex combinations of
functions. Using the functional programming language Scheme, we can define the doubling function by
(define (double x)
(* 2 x)
The user can then run the program and type
(double 5)
which produces an immediate output of 10.
77. a. Write a Scheme function to square a number.
b. What is the output from the following user input?
(double (square 3))
78. Scheme also supports recursion, plus the usual control structures of procedural languages, such as conditional and iterative statements.
a. Given the Scheme function
(define (mystery n)
(cond ((= n 1) 1)
(else (*n (mystery (- n 1))))))
what is the output of
(mystery 4)
b. The “mystery” function is better known as _______.
S e c t I o n 5 . 5 oRdeR oF Magnitude
Function growth
Order of magnitude is a way of comparing the “rate of growth” of different
functions. We know, for instance, that if we compute f (x) = x and g(x) = x
2
for
increasing values of x, the g values will be larger than the f values by an ever
increasing amount. This difference in the rate of increase cannot be overcome
by simply multiplying the f values by some large constant; no matter how large a
constant we choose, the g values will eventually race ahead again. Our experience
indicates that the f and g functions seem to behave in fundamentally different
ways with respect to their rates of growth. In order to characterize this difference
formally, we define a binary relation on functions.
Let S be the set of all functions with domain and codomain the nonnegative
real numbers. We can define a binary relation on S by
f r g 4 there exist positive constants n 0 , c 1 , and c 2 such that, for all x ≥ n 0 ,
c 1 g(x) ≤ f (x) ≤ c 2 g(x)
Relations, Functions, and Matrices
Exercises 77 and 78 involve programming with a functional language. Functional programming languages, as
opposed to conventional (procedural) programming languages such as C++, Java, or Python, treat tasks in
terms of mathematical functions. A mathematical function such as f (x) = 2x transforms the argument 5 into
the result 10. Think of a program as a big function to transform input into output. A functional programming
language contains primitive functions as part of the language, and the programmer can define new functions as
well. Functional programming languages support function composition, allowing for complex combinations of
functions. Using the functional programming language Scheme, we can define the doubling function by
(define (double x)
(* 2 x)
The user can then run the program and type
(double 5)
which produces an immediate output of 10.
77. a. Write a Scheme function to square a number.
b. What is the output from the following user input?
(double (square 3))
78. Scheme also supports recursion, plus the usual control structures of procedural languages, such as conditional and iterative statements.
a. Given the Scheme function
(define (mystery n)
(cond ((= n 1) 1)
(else (*n (mystery (- n 1))))))
what is the output of
(mystery 4)
b. The “mystery” function is better known as _______.
S e c t I o n 5 . 5 oRdeR oF Magnitude
Function growth
Order of magnitude is a way of comparing the “rate of growth” of different
functions. We know, for instance, that if we compute f (x) = x and g(x) = x
2
for
increasing values of x, the g values will be larger than the f values by an ever
increasing amount. This difference in the rate of increase cannot be overcome
by simply multiplying the f values by some large constant; no matter how large a
constant we choose, the g values will eventually race ahead again. Our experience
indicates that the f and g functions seem to behave in fundamentally different
ways with respect to their rates of growth. In order to characterize this difference
formally, we define a binary relation on functions.
Let S be the set of all functions with domain and codomain the nonnegative
real numbers. We can define a binary relation on S by
f r g 4 there exist positive constants n 0 , c 1 , and c 2 such that, for all x ≥ n 0 ,
c 1 g(x) ≤ f (x) ≤ c 2 g(x)