If, g , h are functions such that f(n) = O(g(n)) and g(n) = O(h(n)) prove f(n) = O(h(n))

Question

I'm currently taking my first discrete math class and I'm having a bit of trouble. This is my first encounter with big Oh and I'm having a bit of trouble understanding this particular problem.

I understand proofing that n <= O(n) because I can mathematically prove that there is such constant that will hold true for all values of n >= k

if f, g , h are functions such that f(n) = O(g(n)) and g(n) = O(h(n))

use the definition of big oh given in class to prove that f(n) = O(h(n))

My answer was

|f(n)| <= U1|g(n)| for all n >= k

|g(n)| <= U2|h(n)| for all n >= j

thus

|f(n)| <= U3|h(n)| for all n >= i

Hence f(x) = O(h(x))

I tried to see the professor in her office hours but she said my proofing was incorrect, but would't really say why. I've spent so long on this I don't even know what to do. Any help would be great...

---

Okay! Let me try this again!

|f(n)| <= U1|g(n)| for all n >= k

|g(n)| <= U2|h(n)| for all n >= j

let i equal the largest of either k ∨ j.

let U3 equal U1 * U2

f(n) <= U3|h(n)| for all n >= i

thus

f(n) = O(h(n))

Better?

Answer 1

Using Big O definition:

f = O(g) iff exist c, n0 > 0 such that forall n >= n0 then 0 <= f(n) <= cg(n)

g = O(h) iff exist k, n1 > 0 such that forall n >= n1 then 0 <= g(n) <= kh(n)

Now take the last unequality and divide all members by c: 0 <= f(n)/c <= g(n) and we can substitute g(n) in the second inequality: 0 <= f(n)/c <= kh(n). Finally multiply all members by c and you obtain 0 <= f(n) <= kch(n) that is the definition of f = O(h):

f = O(h) iff exist j, n2 > 0 such that forall n >= n2 then 0 <= f(n) <= jh(n)

In our case it is: n2 = max(n0, n1) and j = ck.