Discrete Mathematics for Computer Science

288 CHAPTER 5 Analysis of Algorithms

y

d

60 d G 4 (n) = n^2 d

50 c F(n) = c d

a F 4 (n) =a d C

40 x F 4 (n)=x c

30 0 F 4 (n) = n d c c c a a

S a

20' d C cc a a a a x X x

10_C ca a

x X

c cd 6qda o " x (^0) i a a a a a ai• O X
2 4 6 8 10

Figure 5.3 Comparison of multiples of a function: G 4 (n) = n^2 , F 4 (n)= n, 2F 4 (n),

3. F 4 (n) (shown a), and 4. F 4 (n).

(b) We will show that for any No and any c, there is at least one n > No where

G 4 (n) < c. F 4 (n)

does not hold. Let No and c be given. If No > c, then pick n = No so that the inequality

fails. Let n > No, and since n > c, n2 > cn. That is, the inequality fails.

If No < c, pick any integer n > c. (We cannot just pick n = c, because we did not

require c to be an integer.) For this n, we have n > No and, again, n^2 > cn, so the inequality

fails. In both cases, we have shown integers n such that n > No that are counterexamples

to the required inequality. 0

Although Example^4 deals with n and n

(^2) , the proof can be used as a model for nk
and nk+1 for k = 3, 4, 5 ..... In Theorem 2 in Section 5.1.2, we will prove that asymptotic

domination is a transitive relation. This result will imply ni E 0(nj) for i, j E N and i < j.

A function F asymptotically dominates a function G if G(n) < c • F(n) for all but

finitely many values of n. It is unimportant what happens on those finitely many values.

In fact, it turns out to be convenient not even to require that F and G be defined on those

values. So, we extend the previous definitions to partial functions that are defined on all

but finitely many values.

Definition 3. Let F, G : N -+ [0, cc) be partial functions. Then, F asymptotically

dominates G if, for some No E N, and some c E (0, cc), for all n > No, both F(n) and

G(n) are defined and G(n) < c .F(n).

In the rest of this section, we assume that F : N [0, cc ) will mean that F is a

partial function and that F(n) is defined for all but finitely many n in N.

There are many partial functions from N to [ 0, cc) with growth rates that are com-

monly discussed but are undefined for finitely many arguments. The following are typical

of such partial functions:

(1) ln(n) is undefined for n = 0 but is defined for all n > 1.

(2) In o ln(n) is undefined for n = 0, 1 but is defined for all n > 2.