Cómo mostrar que f (n) + g (n) = O (max (f (n), g (n)))

Supongo que usted quiso decir “Sea [matemáticas] f (n) [/ matemáticas] y [matemáticas] g (n) [/ matemáticas] funciones de crecimiento. ¿Cómo muestro [matemáticas] f (n) + g (n) \ en O (\ max \ {f (n), g (n) \}). [/ Matemáticas] ”

Este es un problema típico de tarea, así que si es para tarea, inténtelo primero. Aquí vamos.

Apliquemos la definición de Big-Oh. Es decir, necesitamos encontrar una constante real positiva [matemática] c [/ matemática] y un entero positivo [matemática] n_0 [/ matemática] tal que para todos [matemática] n \ geq n_0 [/ matemática], [matemática] f (n) + g (n) \ leq c \ cdot \ max \ {f (n), g (n) \} [/ math]. Elija [matemática] c = 2 [/ matemática], entonces todo lo que queda es determinar [matemática] n_0 [/ matemática]. Bueno, [matemáticas] f (n) + g (n) \ leq \ max \ {f (n), g (n) \} + \ max \ {f (n), g (n) \} = 2 \ cdot \ max \ {f (n), g (n) \} [/ math]. Como esto es cierto para todos [math] n \ geq 1, [/ math] elija [math] n_0 = 1 [/ math]. Por lo tanto, según la definición de Big-Oh, [matemáticas] f (n) + g (n) \ en O (\ max \ {f (n), g (n) \}) [/ matemáticas].