Discrete Mathematics for Computer Science

298 CHAPTER 5 Analysis of Algorithms

(c) Find functions F, G : N --* [0, oc) where O(G) = O(F) but

x-o F(x)G(x)

does not exist.

28. There are many other natural ways to prove Theorem 7.
    (a) Prove Theorem 7 using the result of Exercise 12(a).
    (b) Prove Theorem 7 using the Taylor series for el.
    (c) Prove directly that for all large enough sets X, there are more subsets of X than
    there are k-tuples of elements of X. Use this to give a proof of Theorem 7.


29. Find functions F, G : N - [0, 00) where F e O(G) and G ý O(F) but

lim F(x)

x-*cc G(x)

does not exist.

30. (a) Find two functions F and G such that F 0 O(G) and G 0 O(F). (Hint: For

F 0(G), we need F(n) > 1 • G(n) infinitely often, F(n) > 2. G(n) infinitely

often, and so on. Similarly, for G 0 O(F), we need G(n) > 1 • F(n) infinitely of-

ten, G(n) > 2. F(n) infinitely often, and so on.)

(b) Find two functions, F and G, as in part (a), where in addition F and G are both

strictly increasing.

31. Is it true that for all functions F, O(F) = O(F + 1)? Is it true for all increasing func-

tions F?

rnComplexity of Programs

Recall the questions from the beginning of this chapter:

1. Since you can time a program on only a finite (usually small) number of input data sets,
   how can you (reasonably) estimate the time on other sets of input data?


2. Computer A may do one operation (say, swapping two integers) twice as fast as com-
   puter B. Computer B may do some other operation (say, comparing two real numbers)
   twice as fast as computer A. Can you (reasonably) compare the speeds of two algo-
   rithms without knowing on which machine each program will be run?

3. Can you design your algorithm so that your program will "scale well"-in other words,

so that as the size of the data set increases, the time needed by the program will not

increase too rapidly.

All these questions were used to motivate a comparison of the times taken by algo-

rithms and programs "up to 0." In this section, we will show some basic techniques for

computing that approximate time-without any actual timing.

Before continuing, we will expand on the first question so that you will understand

some of the problems we need to resolve. Suppose you record how much time program

P takes on machine M with data sets of size 10 (T(10)) and a data set of size 100