Let f(n), g(n) and h(n) be three positive functions. For each of the following statements, either...

 

Transcribed Image Text:

Let f(n), g(n) and h(n) be three positive functions. For each of the following statements, either prove that the statement is true or show that the statement is false by providing a counter-example for f, g, and h. (a) f(n) = 0(g(n)) and g(n) = O(h(n)) together imply that f(n) = 0(h(n)) %3D (b) f(n) = 2(g(n)) and g(n) = 2(h(n)) together inmply that f(n) = w(h(n)) %3D (c) f(n) + min{g(n), h(n)} = 0(f(n) + g(n) + h(n)) (d) af(n) = 0(a9(n)) implies g(n) = o(f(n)) Let f(n), g(n) and h(n) be three positive functions. For each of the following statements, either prove that the statement is true or show that the statement is false by providing a counter-example for f, g, and h. (a) f(n) = 0(g(n)) and g(n) = O(h(n)) together imply that f(n) = 0(h(n)) %3D (b) f(n) = 2(g(n)) and g(n) = 2(h(n)) together inmply that f(n) = w(h(n)) %3D (c) f(n) + min{g(n), h(n)} = 0(f(n) + g(n) + h(n)) (d) af(n) = 0(a9(n)) implies g(n) = o(f(n))