Demostrar formalmente que $\Theta(\max(f,g)) = \Theta(f+g)$

Question

Estoy teniendo un tiempo difícil probar que $\Theta(\max(f,g)) = \Theta(f+g) $

donde

$(f+g)(n) = f(n) + g(n) $

y

$(\max{f,g})(n) = \max(f(n), g(n))$

Sé que $\Theta$ es la combinación de los límites superior e inferior, pero me parece que no puede probar esto. Es difícil para mí ver cómo $\Theta$ de la máxima de dos funciones puede ser equivalente a $\Theta$ de las dos funciones que se agregan juntos. Cualquier orientación se agradece. Quisiera saber si me pueden dar más información.

Esta pregunta es similar, pero no acababa de ayuda.

Answer 1

Sin duda, $\max(f,g) \leq f+g$ para $\max(f,g) = O(f+g)$ y sólo queda para establecer el límite inferior.

Si $f = \Theta(g)$, la declaración es trivial, así que asumir $f = O(g)$ y $2 \max(f,g) = 2g \geq f+g$, que implica $\max(f,g) = \Omega(f+g)$, como se desee.

Answer 2

Si $f,g \geq 0$, entonces el $\frac{1}{2}(f+g) \leq \max(f,g) \leq (f+g)$. Reorganización da $ \max(f,g) \leq (f+g) \leq 2 \max(f,g)$.

Sigue que $\Theta(f+g) = \Theta(\max(f,g))$.

Adición: cuando escribimos $a \in \Theta(b)$, que significa que existe $\underline{k}, \overline{k} >0$ y $N$ tal eso si $n\geq N$, entonces el $\underline{k} b(n) \leq a(n) \leq \overline{k} b(n)$. Tenga en cuenta que si $a \in \Theta(b)$ y $\frac{1}{\overline{k}} a(n) \leq b(n) \leq \frac{1}{\underline{k}} a(n)$ y así $b \in \Theta(a)$, por lo tanto es una relación de equivalencia.

Lo anterior muestra que si elegimos $\underline{k} = \frac{1}{2}$, $\overline{k} = 1, N=1$, entonces el $\underline{k}(f(n)+g(n)) \leq \max(f(n),g(n)) \leq \overline{k}(f(n)+g(n))$ y por lo tanto $n \mapsto \max(f(n),g(n)) \in \Theta(n \mapsto f(n)+g(n))$, o, más coloquialmente, $\max(f,g) \in \Theta(f+g)$, y por la observación anterior, también tenemos $f+g \in \Theta(\max(f,g))$.

Answer 3

Solo espero que esto aclara un poco más:

Desea mostrar que $h(x)=\max(f(x),g(x))=\Theta(f(x)+g(x))$. Observar dos casos:

1:

$h(x)=f(x)$, por lo tanto, $f(x) \geq g(x)$. $2 h(x) = 2 f(x) \geq f(x) + g(x)$,

$\Leftrightarrow h(x) \geq \frac{f(x)+g(x)}{2}$

$\Leftrightarrow h(x) = \Omega(f(x)+g(x))$ Esto da el límite inferior.

Siguiente, $h(x)=f(x) \leq f(x)+g(x)=O(f(x)+g(x))$

Por lo tanto, $h(x)=\Theta(f(x)+g(x))$

Caso 2:

$h(x)=g(x)$. Similar al caso 1.