holds for sets.
11. Show that
12. Show that if S 1 ⊆ S 2 , then
.
13. Give conditions on S l and S 2 necessary and sufficient to ensure that
14. Use the equivalence defined in Example 1.4 to partition the set {2, 4, 5, 6, 9,
23, 24, 25, 31, 37} into equivalence classes.
15. Show that if f (n)= O (g (n)) and g (n) = 0 (f (n)), then f (n) = Θ (g (n)).
16. Show that 2 n = O (3 n ) but 2 n ≠ Θ (3 n ).
17. Show that the following order-of-magnitude results hold.
(a) n 2 + 5 log n = O (n 2 ).
(b) 3 n = O (n!).
(c) n!= O (n n ).
18. Prove that if f (n) = O (g (n)) and g (n)= O (h (n)), then f (n) = O (h (n)).
19. Show that if f (n)= O (n 2 ) and g (n) = O (n 3 ), then
and
20. Assume that f(n) = 2n 2 + n and g (n) = O (n 2 ). What is wrong with the
following argument?
so that