Para cualesquiera números racionales r y s, si r s, entonces x r es O(x s). 11.2.2 En la figura 11.2.2, de la siguiente página, se muestra geométr...

Para cualesquiera números racionales r y s, si r s, entonces x r es O(x s). 11.2.2 En la figura 11.2.2, de la siguiente página, se muestra geométricamente la relación entre las gráficas de varias funciones potencia positivas de x para x 1. 730 Capítulo 11 Análisis de la eficiencia de un algoritmo x y y = x3 y = x2 y = xy = x3/2 y = x1/2 y = x2/3 y = x1/3 Si r s, la gráfica de y = xr se encuentra abajo de la gráfica de y = x s para x 1. 1 2 3 4 Figura 11.2.2 Gráficas de potencias de x para x 1 Órdenes de funciones polinomiales El siguiente ejemplo muestra cómo emplear la propiedad (11.2.1) para deducir una desigualdad polinomial. Ejemplo 11.2.3 Una desigualdad polinomial Demuestre que para cualquier número real x, si x 1, entonces 3x3 2x 7 12x3. Solución Suponga que x es un número real y x 1. Entonces por la propiedad (11.2.1), x x3 y 1 x3. Multiplique la desigualdad de la izquierda por 2 y la desigualdad de la derecha por 7 para obtener 2x 2x3 y 7 7x3. Ahora sume 3x3 3x3, 2x 2x3 y 7 7x3 para obtener 3x3 2x 7 3x3 2x3 7 x3 12x3. El método del ejemplo 11.2.3 se utiliza en el próximo ejemplo (más compactamente) para demostrar que una función polinomial tiene un cierto orden. Ejemplo 11.2.4 Uso de las definiciones para demostrar que una función polinomial con coeficientes positivos tiene un cierto orden Use las definiciones de omega mayúscula, O mayúscula y Theta mayúscula para demostrar que 2x4 3x3 5 es (x4). Solución Defina las funciones f y g como sigue. Para todos los números reales no-negativos x, f (x) 2x4 3x3 5 y g(x) x4. Observe que para todos los números reales x 0, 2x4 2x4 3x3 5, porque 3x3 5 0 para x 0. 11.2 Notaciones O, y 731 y así 2 x4 2x4 3x3 5 porque son positivos todos los términos en ambos lados de la desigualdad. Sean A 2 y a 0. Entonces A x4 2x4 3x3 5 para toda x a, por tanto, por definición de notación , 2x4 3x3 5 es (x4). También para x 1, 2x4 + 3x3 + 5 ≤ 2x4 + 3x4 + 5x4 ⇒ 2x4 + 3x3 + 5 ≤ 10x4 ⇒ |2x4 + 3x3 + 5| ≤ 10|x4| porque por (11.2.1), x3 x4 y 1 x4 y así 3x3 3x4 y 5 5x4, porque 2 3 5 = 10, porque todos los términos en ambos lados de la desigualdad son positivos. Sean B 10 y b 1. Entonces 2x4 3x3 5 B x4 para todo x b, y así, por definición de la notación O, 2x4 3x3 5 es O(x4). Como 2x4 3x3 5 es (x4) y O(x4), entonces por el teorema 11.2.1, también es (x4). La técnica utilizada en el ejemplo 11.2.4 se puede generalizar para demostrar que cualquier polinomio con coeficientes no-negativos es la omega mayúscula de su término a la más alta potencia. Los dos ejemplos siguientes prueban que este resultado puede ser válido para un polinomio tanto para coeficientes negativos como positivos. Ejemplo 11.2.5 Una aproximación O para un polinomio con algunos coeficientes negativos a. Use la definición de la notación O para demostrar que 3x3 ฀ 1 000x ฀ 200 es O(x3). b. Demuestre que 3x3 ฀ 1 000x ฀ 200 es O(xs) para todos los enteros s 3. Solución a. De acuerdo a la desigualdad del triángulo para el valor absoluto (teorema 4.4.6), a b a b para todos los números reales a y b. Si se sustituye ฀b en lugar de b, el resultado es a ฀ b a (฀b) a ฀b a b , o a ฀ b a b . Se tiene que para todos los números reales x 1, |3x3 − 1000x − 200| ≤ |3x3| + |1000x | + |200| ⇒ |3x3 − 1000x − 200| ≤ 3x3 + 1000x + 200 ⇒ |3x3 − 1000x − 200| ≤ 3x3 + 1000x3 + 200x3 ⇒ |3x3 − 1000x − 200| ≤ 1203x3 ⇒ |3x3 − 1000x − 200| ≤ 1203|x3| porque todos los términos en el lado derecho de la desigualdad son positivos cuando x 1, porque debido a (11.2.1), x x3 y 1 x3 y así 1 000x 1 000x3 y 200 200x3, porque 3 1 000 200 1 203, porque x3 es positivo. desigualdad del triángulo. Nota Cuando se coloca la flecha de implicación, , al inicio de un renglón, significa que cada número x que hace válida la desigualdad del renglón anterior, también hace verdadera la desigualdad del renglón dado. 732 Capítulo 11 Análisis de la eficiencia de un algoritmo Sean b 1 y B 1 203. Entonces 3x3 ฀ 1 000x ฀ 200 B x3 para todos los números x b. Así, por definición de la notación O, 3x3 ฀ 1 000x ฀ 200 es O(x3). b. Suponga que s es un entero con s 3. Por la propiedad (11.2.1), x3 x s para todos los números reales x 1. Así B x3 B xs para todos los números reales x b (porque b 1) y entonces por el inciso a), 3x3 ฀ 1 000x ฀ 200 B xs para todos los números reales x b. Por tanto, por definición de la notación O, 3x3 ฀ 1 000x ฀ 200 es O(xs) para todos los enteros s 3. Ejemplo 11.2.6 Una aproximación omega mayúscula para un polinomio con algunos coeficientes negativos a. Use la definición de la notación para demostrar que 3x3 ฀ 1 000x ฀ 200 es (x3). b. Demuestre que 3x3 ฀ 1 000x ฀ 200 es (x r) para todos los enteros r 3. Solución a. Para demostrar que 3x3 ฀ 1 000x ฀ 200 es (x3), necesita encontrar números a y A tales que A x3 3x3 ฀ 1 000x ฀ 200 para todos los números reales x a. El ejercicio 27, al final de la sección, muestra que el siguiente procedimiento para elegir a siempre producirá una A que dará el resultado deseado. Elija a como sigue: Sume los valores absolutos de los coeficientes de los términos de más bajo orden de 3x3 ฀ 1 000x ฀ 200, divida entre el valor absoluto del término de más alta potencia y multiplique el resultado por 2. El resultado es a 2(1 000 200) 3, el cual es igual a 800. Si sigue los pasos que se muestran a continuación verá que cuando a se elige de esta manera, A se puede tomar como la mitad del valor absoluto de la más alta potencia del polinomio. Entonces, suponga que x a. Por tanto x 800 x 2 1 000 200 3 x 2 1 000 3 2 200 3 x 2 1 000 3 1 x 2 200 3 1 x2 3 2 x3 1 000x 200 3x3 ฀ 3 2 x3 1 000x 200 3x3 ฀ 1 000x ฀ 200 3 2 x3 3x3 ฀