Regla de la suma de la notación Big O

Question

Entiendo que al añadir funciones, el comportamiento está dominado por la mayor potencia. Pero lo que me cuesta es entender la prueba. Podría alguien ayudarme paso a paso a explicar la prueba que hay detrás de $T_1(n) + T_2(n) = O(max (f(n), g(n)))$ ? Muchas gracias.

Answer 1

Dado $T_1(n)=O(f(n))$ y $T_2(n)=O(g(n))$ Debemos demostrar que $$T_1(n)+T_2(n)=O(\max(f(n),g(n))\tag0$$

• Escribe exactamente lo que dice la primera hipótesis: existe una constante $C_1$ y un índice $N_1$ tal que $$|T_1(n)| \le C_1f(n)\quad \text{when } n\ge N_1 \tag1$$

• Escribe exactamente lo que dice el segundo supuesto: existe una constante $C_2$ y un índice $N_2$ tal que $$|T_2(n)| \le C_2g(n)\quad \text{when } n\ge N_2 \tag2$$

• Prepárese para combinar (1) y (2) introduciendo $N=\max(N_1,N_2)$ y $C=\max(C_1,C_2)$ .

• Suma (1) y (2): $$ |T_1(n)|+|T_2(n)|\le C_1f(n)+C_2g(n) \le C(f(n)+g(n))\quad \text{when } n\ge N \tag3 $$

• Comprueba que para dos números reales cualesquiera $a,b$ tenemos $$a+b\le 2\max(a,b)\tag4$$

• Utilice (4) en (3) para obtener $$ |T_1(n)|+|T_2(n)|\le 2C\max(f(n),g(n))\quad \text{when } n\ge N \tag5 $$

• Concluya que (0) se mantiene.

Answer 2

Considerando las funciones no negativas podemos decir más, que los conjuntos $O(f)+O(g),O(f+g),O(\max(f,g))$ son iguales, es decir, la igualdad que podemos entender como igualdad entre conjuntos no sólo como " $\subset$ ", es decir, en una dirección. Así que tenemos $$O(f)+O(g)=O(f+g)=O(\max(f,g))$$ como conjuntos.

Para la prueba, por ejemplo, basta con utilizar $f+g\leqslant 2\cdot \max(f,g)\leqslant 2\cdot (f+g)$