In: Computer Science
Which of these statements are true and which are false?
(a) If f(n) = Θ(g(n)) and g(n) = Θ(h(n)), then h(n) = Θ(f(n))
(b) If f(n) = O(g(n)) and g(n) = O(h(n)), then h(n) = Ω(f(n))
(c) If f(n) = O(g(n)) and g(n) = O(f(n)) then f(n) = g(n)
(d) 100n = Ω(n2)
(e) In the merge-sort execution tree, roughly the same amount of work is done at each level of the tree.
(f) An algorithm is randomized if its behavior is determined in part by values produced by a random-number generator.
(g) Quicksort can be used as the auxiliary sorting routine in radix sort, because it operates in place.