Question

Prove that (f = O(g)] ^ (g = O(h)] = f = O(h).

Answer 1

Proof:      
        Since f = O(g) and g = O(h) there exist positive integers k0, N0, k1,N1

s.t. f(n) <= k0g(n) for all n >= N0       ... (1)
and  g(n) <= k1h(n) for all n >= N1       ... (2)

Now let N = max {N0, N1}.  Then (1) and (2) both hold when n>= N
and we have f(n) <= k0g(n) for all n>= N.

        Since g(n) <= k1h(n) for all n>= N, this implies that 

        f(n) <= k0(k1h(n)) = k0k1h(n)  for all n >= N where k0k1 > 0 is a 
constant.  

Let k0k1 = k.  Then f(n) <= kh(n) for all n>= N.  So f = O(h)