Demuestre lo siguiente: si $f(n)$ es $O(g(n))$ y $g(n)$ es $O(h(n))$ entonces $f(n)$ es $O(h(n))$

Question

Entiendo que $f(n) \leq Ng(n)$ y $g(n) \leq Nh(n)$ tan obviamente $f(n) \leq Nh(n)$ pero, ¿cómo se puede demostrar esto utilizando la semántica adecuada (utilizando grandes $O$ notación)?

Answer 1

Bueno, cuando $f(n)$ es $O(g(n))$ debe tener una constante asociada $K_f$ y algunos $N_f$ . Entonces, cuando $g(n)$ es $O(h(n))$ tiene una constante asociada $K_h$ y algunos $N_h$ .

Tome el mayor de los dos $N$ (o su suma, o su producto, etc.) y tomar $K_f K_h$ para que sea la nueva constante. Esto le dará la asintótica $n$ y $k$ para que $f(n) < kh(n)$ para todas las $n$ .