# Thread: "order of" equality question

1. ## "order of" equality question

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.

2. Originally Posted by inneedofhelp
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.
what do you mean by O(g(n)) and O(h(n))?

3. Originally Posted by Jhevon
what do you mean by O(g(n)) and O(h(n))?
He means the big O notation.*
(I am too lazy to post proofs now).

*)I hate that notation with a love.

4. Originally Posted by inneedofhelp
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.
$\displaystyle f(n)=O(g(n))$ means there exist $\displaystyle n_1$ and $\displaystyle M_1$ such that:

$\displaystyle |f(x)| \le M_1|g(n)|\ \forall n>n_1$

and $\displaystyle g(n)=O(g(n))$ means there exist $\displaystyle n_2$ and $\displaystyle M_2$ such that:

$\displaystyle |g(x)|\le M_2|h(n)|\ \forall n>n_2$

Hence:

$\displaystyle |f(x)|\le M_1 M_2 |h(n)|\ \forall n> \max(n_1,n_2)$

Therefore $\displaystyle f(n)=O(h(n))$

RonL