Suppose we have three functions f(n), g(n), and h(n) such that f(n) = O(g(n)) and g(n) = O(h(n)). Must it be the case that f(n) = O(h(n))? Explain why or give a counterexample showing why not.
Suppose we have three functions f(n), g(n), and h(n) such that f(n) = O(g(n)) and g(n) = O(h(n)). Must it be the case that f(n) = O(h(n))? Explain why or give a counterexample showing why not.
Suppose we have three functions f(n), g(n), and h(n) such that f(n) = O(g(n)) and g(n) = O(h(n)). Must it be the case that f(n) = O(h(n))? Explain why or give a counterexample showing why not.
means there exist and such that:
and means there exist and such that:
Hence:
Therefore
RonL
Last edited by CaptainBlack; September 3rd 2007 at 10:31 PM.