Chapter Review 323
by means of solving Exercises 1 through 10. (Remember to show inequality.)
- Prove that 0(1) c 0(log(n)).
- Prove that 0(log(n)) C O(/ni).
3. Prove that 0(,/I-) C 0(n).
4. Prove that 0(n) c 0(n log(n)).
- Prove that 0(n log(n)) c 0(n^2 ).
- Prove that 0(n^2 ) C 0(2n).
- Prove that 0(2n) C 0(n .2n).
- Prove that 0(n • 2n) C 0(3n).
- Prove that 0(3n) C 0(n!).
- Prove that 0(n!) c 0(nn).
5.6.4 Using Discrete Mathematics in Computer Science
- Let F 1 , F 2 , G 1 , G 2 : N -* [0, oc). Prove the following, or find counterexamples:
(a) If F 1 E O(GI) and F 2 c O(G 2 ), then F1 + F 2 E O(G 1 + G 2 ).
(b) If F 1 E O(GI) and F 2 E O(G 2 ), then I F 1 - F 2 1 e 0(1 G 1 - G 2 I).
(c) If F 1 E O(G 1 ) and F 2 E O(G 2 ), then F 1 - F 2 e O(G 1 • G 2 ) where F 1 • F 2 (x) =
F 1 (x) F 2 (x).
(d) If F 1 E O(Gl) and F 2 E O(G 2 ), then FI/F 2 E O(G1/G 2 ) where F 1 /F 2 (x) =
Ft(x)/F 2 (x) provided F 2 (x), G 2 (x) 0 0.
(e) If F 1 e O(Ga) and F 2 e O(G 2 ), then F 1 o F 2 e O(G 1 o G 2 ).
- Use Exercise 1 and the chain of set inclusions proven in Section 5.6.3 to determine a
simpler bound for the complexity of the following functions:
(a) 2n^2 + n - nlog(n)
(b) n +n2n + e^2
(c) n3(n2 + 3n)
(d) 2n(n2 - 2n)
(e) 3n2 - 2n + 5 + n½1og(n)
- (a) Find the complexity of the following algorithm for computing factorials:
INPUT: n E N
OUTPUT: n!
3=1
for i = 1 to n
X = x
print x
