Discrete Mathematics for Computer Science

290 CHAPTER 5 Analysis of Algorithms

NG, and NH that we do not have. However, to verify that H e O(F), we were not required

to find the smallest possible constants c and NO; we were only required to find some such

constants.

In Theorem 3 we see that if two functions G and H are both asymptotically dominated

by a third function F, then both G + H and I G - H I are functions that are asymptotically

dominated by F. For example, if G(n) = n^2 , H(n) = n, and F(n) = n3, then n^2 + n

O(n3).

Theorem 3. Let F, G, H : - [ 0, oo), with G E O(F) and H E O(F). Then, G +

H E O(F) and I G - HI E O(F).

Proof Since G e O(F), there exist constants CG E [0, oo) and NG e N such that for

all n > NG, F(n) and G(n) are both defined and G(n) < cG • F(n). Similarly, there are

constants CH E [0, oo) and NH c N such that for all n > NH, F(n) and H(n) are both

defined and H(n) < cH • F(n).

Let c = cG + CH, and let No be the maximum of NG and NH. Then, for all n > No,

both F(n) and G(n) + H(n) are defined, and

G(n) + H(n) < cG -F(n) + cH • F(n) = c. F(n)

Furthermore, for all n > No, I G(n) - H(n) I is defined, and

I G(n)-H(n)I < IG(n) +IH(n)I = G(n)+H(n) < c.F(n)

Hence, G + H e O(F) and IG - H E o(F). U

Corollary 2: Let F, G 1 , G 2 ... , Gk : N - [0, cc) for some k e N such that for 1 <

i < k, each Gi E O(F). Then, for any real numbers at, a2 ... , ak,

IalGI + a2G2 +... + akGk l e O(F)

Proof Use induction on k. Separate arguments are needed depending on whether ak is

positive (or zero) or negative. The results in both Theorems 1 and 2 are used. The details

are left as an exercise for the reader. U

We can use our results to define an equivalence relation that is closely related to

asymptotic domination.

Theorem 4. Let F, G : N - [0, oo).

(a) Fe O(G) if and only if O(F) C O(G).

(b) 0(F) = 0(G) if and only if F E 0(G) and G e 0(F).

(c) The relation 0, defined as {(F, G) : 0(F) = 0(G)}, is an equivalence relation.

Proof This proof is left as an exercise for the reader. U

With the proof of Theorem 4(c) we see what condition is needed to define a symmetric

relation based on asymptotic domination. We showed that in general, asymptotic domina-

tion is reflexive and transitive, but the functions in Example 4 tell us there is no hope of

making the relation symmetric. The relation 0 tells us there is an equivalence relation that

depends on a slightly stronger relation than asymptotic domination. An ongoing problem

in computer science is to determine what functions are in each equivalence class of the

equivalence relation 0.