Demostrar que O(max(g(x), f(x)) está en O(g(n) + f(n))

Question

Esperaba que alguien pudiera verificar que mi prueba es correcta. Bien, aquí vamos.

$$max(g(n), f(n)) \le 1(g(x) + f(x)) \text{ for all x > 0} $$ $$\text{Let A = 1 and }n_0 = 1$$ $$max(g(n), f(n)) \le A(g(x) + f(x)) \text{ for all n >=}n_0 $$ por la definición de la notación Big O, hemos demostrado que $$ max(g(n),f(n))~=~O(f(n)+g(n))$$ y por lo tanto $$O(max(g(n),f(n))~\subseteq~O(f(n) + g(n))$$

Answer 1

Esto no es realmente correcto. Usted ha demostrado que $\max(f,g)=O(f,g)$ . Para demostrar que $O(\max(f,g))\subseteq O(f+g)$ hay que demostrar que si $h=O(\max(f,g))$ entonces $h=O(f+g)$ .

Esto es cierto por un razonamiento similar al que usted ha dicho. El razonamiento correcto es que $\exists N,k$ tal que $\forall n>N$ , $h(n)\leq k\max(f(n),g(n))\leq k(f(n)+g(n))$