3.1 − 1
Let f(n), g(n) be asymptotically nonnegative. Show that max(f(n), g(n)) = Θ(f(n) + g(n)). This
means that there exists positive constants c
1
, c
2
and n
0
such that,
0 6 c
1
(f(n) + g(n)) 6 max(f(n), g(n)) 6 c
2
(f(n) + g(n))
for all n > n
0
.
Selecting c
2
= 1 clearly shows the third inequality since the maximum must be smaller than
the sum. c
1
should be selected as 1/2 since the maximum is always greater than the weighted
average of f(n) and g(n). Note the significance of the “asymptotically nonnegative” assumption.
The first inequality could not be satisfied otherwise.
3.1 − 4
2
n+1
= O(2
n
) since 2
n+1
= 2 · 2
n
6 2 · 2
n
! However 2
2n
is not O(2
n
): by definition we have
2
2n
= (2
n
)
2
which for no constant c asymptotically may be less than or equal to c ·2
n
.
3 − 4
Let f(n) and g(n) be asymptotically positive functions.
a. No, f(n) = O(g(n)) does not imply g(n) = O(f(n)). Clearly, n = O(n
2
) but n
2
6= O(n).
b. No, f(n) + g(n) is not Θ(min(f(n), g(n))). As an example notice that n + 1 6= Θ(min(n, 1)) =
Θ(1).
c. Yes, if f(n) = O(g(n)) then lg(f(n)) = O(lg(g(n))) provided that f(n) > 1 and lg(g(n)) > 1
are greater than or equal 1. We have that:
f(n) 6 cg(n) ⇒lg f(n) 6 lg(cg(n)) = lg c + lg g(n)
To show that this is smaller than b lg g(n) for some constant b we set lg c + lg g(n) = b lg g(n).
Dividing by lg g(n) yields:
b =
lg(c) + lg g(n)
lg g(n)
=
lg c
lg g(n)
+ 1 6 lg c + 1
The last inequality holds since lg g(n) > 1.
d. No, f(n) = O(g(n)) does not imply 2
f(n)
= O(2
g(n)
). If f(n) = 2n and g(n) = n we have that
2n 6 2 · n but not 2
2n
6 c2
n
for any constant c by exercise 3.1 − 4.
e. Yes and no, if f(n) < 1 for large n then f(n)
2
< f(n) and the upper bound will not hold.
Otherwise f(n) > 1 and the statement is trivially true.
f. Yes, f(n) = O(g(n)) implies g(n) = Ω(f(n)). We have f(n) 6 cg(n) for positive c and thus
1/c · f(n) 6 g(n).
g. No, clearly 2
n
66 c2
n/2
= c
√
2
n
for any constant c if n is sufficiently large.
h. By a small modification to exercise 3.1−1 we have that f(n)+o(f(n)) = Θ(max(f(n), o(f(n)))) =
Θ(f(n)).
5
