Introduction to Algorithms

Chapter03 - Home
Exercises: 1 - 2 - 3 - 4 - 5 - 6 - 7 - 8 - 9 - 10 - 11 - 12 - 13 - 14 - 15 - 16 - 17 - 18 - 19 - 20 - 21

Exercise. This is the solution to exercise 3.1-1 in the book.

Solution. We have that

Θ(f(n) + g(n)) = {h(n)}

with

0 c1 f(n) + g(n) h(n) c2 f(n) + g(n)

Is max(f(n),g(n)) in the set of these functions? Since both f(n) and g(n) are asymptotically non-negative, then n n0 such that f(n) 0 and g(n) 0. Therefore, we have that (for n n0):

f(n) + g(n) f(n) 0f(n) + g(n) g(n) 0

Since max(f(n),g(n)) equals either f(n) or g(n) then

0 max(f(n),g(n)) f(n) + g(n)

We have that:

1 2f(n) 1 2max(f(n),g(n))

1 2g(n) 1 2max(f(n),g(n))

Hence,

0 1 2 f(n) + g(n) max(f(n),g(n))

Therefore

0 1 2 f(n) + g(n) max(f(n),g(n)) f(n) + g(n)

Hence,

max(f(n),g(n)) = Θ(f(n) + g(n))

with c1 = 1 2 and c2 = 1 and some n0.