Dominancia de funciones, orden de crecimiento y propiedades#
Introducción#
Ya tenemos las definiciones básicas de las notaciones asintóticas que estamos utilizando: \(O\) grande, \(\Omega\) y \(\Theta\). A grandes rasgos:
\(f(n)=O(g(n))\) nos dice que \(f(n)\) es más chiquita que un múltiplo de \(g(n)\) para \(n\) suficientemente grande.
\(f(n)=\Omega(g(n))\) nos dice que \(f(n)\) es más grande que un múltiplo de \(g(n)\) para \(n\) suficientemente grande.
\(f(n)=\Theta(g(n))\) nos dice que \(f(n)\) queda entre dos múltiplos de \(g(n)\) para \(n\) suficientemente grande.
Es algo impráctico trabajar directamente con las definiciones de \(O\), \(\Omega\) y \(\Theta\), pues requieren de buscar constantes \(c\) y \(n_0\), lo cual no siempre es sencillo. Lo que haremos ahora es entender algunas propiedades teóricas de estas notaciones para poder trabajarlas de manera mucho más ágil. Nos interesa traducir estas notaciones a límites (para poder usar todo lo que sabemos de límites) y saber cómo se trabaja con la suma y el producto en estas notaciones asintóticas.
En toda esta entrada nos enfocaremos principalmente en la notación \(O\) grande y pensaremos en funciones de los reales positivos a los reales positivos. Sin embargo, los resultados que veamos se pueden adaptar fácilmente a las notaciones \(\Omega\), \(\Theta\) y cuando las funciones son positivas sólo a partir de un real.
Propiedades de \(O\) grande y dominancia de funciones#
Un resultado muy útil para saber si tenemos \(f(n)=O(g(n))\) es traducir la definición a un límite. Más precisamente, a un límite superior.
Lema. (el truco del \(\limsup\)) Se tiene que \(f(n)=O(g(n))\) si y sólo si
En particular, si \(\lim_{n\to \infty} \frac{f(n)}{g(n)}\) existe y es finito, entonces \(f(n)=O(g(n))\).
Demostración. Recordemos que por definición
Si \(f(n)=O(g(n))\), entonces existen constantes \(c\) y \(n_0\) tales que \(f(n)\leq cg(n)\) para \(n\geq n_0\), de donde \(\frac{f(n)}{g(n)}\leq c\). Así, si \(n\geq n_0\), \(c\) es una cota superior para el conjunto \(\{\frac{f(m)}{g(m)}: m\geq n\}\), por lo que por definición de supremo tenemos \(\sup_{m\geq n} \frac{f(n)}{g(n)} \leq c\) y entonces \(\limsup_{n\to \infty} \frac{f(n)}{g(n)} \leq c < \infty\).
Por otro lado, supongamos que \(\limsup_{n\to \infty} \frac{f(n)}{g(n)} = C < \infty\). Tomando \(\epsilon=1\), existe una \(n_0\) tal que si \(n\geq n_0\), entonces \(\sup_{m\geq n} \frac{f(m)}{g(m)} < C+1\). En particular esto funciona para \(n=n_0\). Como el supremo es una cota para todo \(m\geq n_0\), para dichas \(m\) tenemos \(\frac{f(m)}{g(m)}<C+1\), que puede rescribirse como \(f(m)<(C+1)g(m)\). Así, tomando el \(n_0\) dado y \(c=C+1\) obtenemos el resultado deseado. \(\square\)
Veamos algunos ejemplos de cómo se utiliza este lema.
Ejemplo. Se tiene que \(\sqrt{n^3+2n+1}=O\left(\sqrt{3n^3}\right)\). Esto es inmediato por el lema anterior pues
Aquí estamos usando propiedades estándar de cálculo: raiz cuadrada es continua, límite de la suma es suma de los límites (cuando existe), etc. \(\square\)
Otra propiedad que en ocasiones resulta de utilidad es que la notación \(O\) grande es transitiva.
Proposición. Si \(f(n)=O(g(n))\) y \(g(n)=O(h(n))\), entonces \(f(n)=O(h(n))\).
Demostración. Tomemos \(c_1\), \(n_1\) las constantes que sirven para demostrar lo primero y \(c_2\), \(n_2\) las constantes que sirven para demostrar lo segundo. Tomemos \(c=c_1c_2\) y \(n_0=\max(n_1,n_2)\). Si \(n>n_0\), entonces tenemos \(f(n)\leq c_1g(n) \leq c_1c_2h(n)=ch(n)\). \(\square\)
Un último concepto por mencionar relacionado con la notación \(O\) grande es el de dominancia.
Definición. Diremos que la función \(g\) domina a la función \(f\) si \(f(n)=O(g(n))\) pero no sucede que \(g(n)=O(f(n))\). También decimos que \(g(n)\) tiene un mayor orden de magnitud. En símbolos, escribiremos \(g\gg f\).
La intuición detrás de esta definición es que asintóticamente la función \(g\) es mucho más grande que \(f\). Tan grande, que no es posible ni siquiera compensar este tamaño con una constante multiplicativa.
Proposición. La relación «dominar a» es una relación transitiva, es decir, si \(h\gg g\) y \(g\gg f\), entonces \(h\gg f\).
Demostración. El hecho de que \(f(n)=O(h(n))\) se deduce de la proposición anterior. Debemos también ver que no es cierto que \(h(n)=O(f(n))\). Procedamos por contradicción. Si \(h(n)=O(f(n))\), como además tenemos \(g=O(h(n))\), entonces tendríamos por transitividad de la notación \(O\) grande que \(g=O(f(n))\). Pero esto da una contradicción a \(g\gg f\), en donde \(g=O(f(n))\) se prohíbe. \(\square\)
La dominancia de funciones es fundamental para simplificar el análisis asintótico pues, como veremos un poco más abajo, usualmente los términos dominantes son los que prevalecen al hacer operaciones.
Se pueden demostrar todas las siguientes dominancias:
Hasta la izquierda tenemos \(n!\), que es una función muy grande. Luego vienen las exponenciales, en donde la base importa mucho para saber cuál domina. Cualquier exponencial le gana a cualquier polinomio, y en los polinomios ganan los de mayor grado. Por ahí aparece \(n\log n\) de manera especial, pues es una función importante en el análisis de algoritmos. Más pequeño que \(n\) tenemos a las raíces de \(n\) y todavía más pequeño a los logarimos, o logaritmos de logaritmos. La función más pequeña posible de las que nos interesan es la constante \(1\).
Podría parecer que aún nos faltan muchas funciones, por ejemplo ¿dónde quedan en este orden funciones como \(n^5+3n^2+n\log n+\sqrt{n}\)? Sin embargo, como veremos a continuación, esta cadena ya es de mucha ayuda para entender cómo son muchas otras funciones asintóticamente.
Órdenes de magnitud#
Definición. Diremos que \(f\) y \(g\) tienen el mismo orden de magnitud si \(f(n)=\Theta(g(n))\).
La intuición detrás de esta definición es que \(f\) y \(g\) son indistinguibles, salvo constantes multiplicativas, cuando \(n\) se hace muy grande.
Proposición. La relación «tener el mismo orden de magnitud» es una relación de equivalencia, es decir:
Es reflexiva: \(f(n)=\Theta(f(n))\).
Es simétrica: si \(f(n)=\Theta(g(n))\), entonces \(g(n)=\Theta(g(n))\).
Es transitiva: si \(f(n)=\Theta(g(n))\) y \(g(n)=\Theta(h(n))\), entonces \(f(n)=\Theta(h(n))\).
La demostración es sencilla y se deja como ejercicio. Esta proposición lo que nos dice es que podemos «agrupar» a las funciones de acuerdo a su orden de magnitud.
Cuando estamos estudiando una función \(f\), lo ideal es encontrar una función \(g\) con exactamente el mismo orden de magnitud, pero mucho más sencilla. Si queremos comparar a dos funciones, nos conviene simplificar ambas. De ahí, usualmente será evidente si ambas funciones tienen el mismo orden de magnitud, o bien, si alguna domina a la otra.
Suma en la notación O grande#
Cuando estudiamos asintóticamente la suma de funciones mediante la notación \(O\) grande, los términos de mayor orden son los que prevalecen. Hay muchas variantes para escribir esto de manera formal. A continuación presentamos una versión para la notación \(O\) grande.
Proposición. Si se tienen funciones \(f\) y \(g\) tales que \(f(n)=O(g(n))\), entonces \(f(n)+g(n)=O(g(n))\).
Demostración. De la hipótesis \(f(n)=O(g(n))\) tenemos constantes \(c>0\) y \(n_0\) tales que \(f(n)\leq cg(n)\) para \(n\geq n_0\). Así, tenemos que \(f(n)+g(n)\leq (c+1)g(n)\) para \(n\geq n_0\), como queremos. \(\square\)
Si \(g\) domina a \(f\), tenemos en particular que \(f(n)=O(g(n))\), por lo que en este caso la suma también es \(O(g(n))\). En este caso, de hecho se puede mostrar que \(f(n)+g(n)=\Theta(g(n))\). Si bien la proposición y estas observaciones están escritas de dos en dos, con un argumento inductivo se puede probar lo siguiente:
Corolario. En una suma de funciones, el comportamiento asintótico es el de la función con mayor orden.
Ejemplo. Tomemos la función \(f(n)=3n^3+2n^2-5n+7\). Para \(n\geq 0\), tenemos que \(f(n)\leq 3n^3+2n^2+7\), lo cual nos permite quitar el término negativo. Luego, tenemos que \(2n^2=O(3n^3)\) y que \(7=O(3n^3)\). Así, el término de mayor orden es \(3n^3\) y por lo tanto \(f(n)=O(3n^3)\). Además, \(3n^3=O(n^3)\). Por la transitividad de la notación \(O\) tenemos entonces que \(f(n)=O(n^3)\).
Esto es una buena cota asintótica superior pues la función dentro de la notación \(O\) es muy sencilla. Un poco más de trabajo muestra que también \(f(n)=\Omega(n^3)\), de modo que \(f(n)=\Theta(n^3)\). \(\square\)
Producto en la notación O grande#
El producto de funciones también es muy sencillo de entender en la notación \(O\) grande. Recuerda que en todos estos temas estamos tomando funciones positivas. Si se toman funciones negativas, hay que ser un poco más cuidadoso y tomar valores absolutos.
Proposición. Si \(f(n)=O(F(n))\) y \(g(n)=O(G(n))\), entonces \(f(n)g(n)=O(F(n)G(n))\).
La demostración es sencilla pues si \(c_1\), \(n_1\) son las constantes que funcionan para lo primero y \(c_2\), \(n_2\) son las constantes que funcionan para lo segundo, es facil ver tras multiplicar las desigualdades correspondientes que \(c=c_1c_2\) y \(n_0=\max(n_1,n_2)\) son las constantes que funcionan para la conclusión.
Al igual que en el caso de la suma, el resultado también se vale para más factores.
Ejemplo. Podemos combinar ambas expresiones para dar cotas superiores asintóticas para expresiones que parecerían muy complicadas. Por ejemplo, consideremos la siguiente función:
En el primer factor podemos usar la propiedad de la suma. Notamos que el término de orden mayor es \(2n^3\), y que es \(O(n^3)\). De este modo, el primer factor es \(O(n^3)\).
En el segundo factor el término de orden mayor es \(\sqrt{7n+1}\), que es \(O(\sqrt{n})\) así que por la propiedad de la suma todo el factor es \(O(\sqrt{n})\).
Finalmente, el tercer factor es \(O(n)\) por razones similares a las anteriores.
Hasta el final podemos usqr entonces la regla del producto para concluir que
Veamos un último problema en donde se aprovechan ambas propiedades de la notación \(O\) y propiedades similares para otras notaciones asintóticas.
Problema. Demuestra que la siguiente expresión
es \(\Theta(n^6)\).
Solución. Una forma de proceder sería encontrar una fórmula para la suma de las potencias quintas de los primeros \(n\) naturales. Esto es un posible camino, pero toma el esfuerzo de conjeturar una fórmula y demostrarla (quizás por inducción). Después, habría que estudiar esa fórmula asintóticamente.
Hay una forma más sencilla de proceder si únicamente nos interesa conocer el comportamiento asintótico. Cada uno de los términos es menor o igual a \(n^5\) y hay \(n\) términos, de modo que la suma está acotada superiormente por \(n^6\). Esto muestra que la expresión es \(O(n^6)\). Por otro lado, a partir de la mitad de los términos, hacia la derecha cada uno de los términos es mayor o igual a \(\left(\frac{n}{2}\right)^5\). Así, hay por lo menos \(\frac{n-1}{2}\) términos, cada uno de tamaño al menos \(\left(\frac{n}{2}\right)^5\). De esta forma, la expresión es mayor o igual a \(\frac{n-1}{2}\cdot \left(\frac{n}{2}\right)^5\). El primer término es \(\Omega(n)\) y el segundo \(\Omega(n^5)\), de modo que el producto es \(\Omega(n^6)\).
Como la expresión es \(O(n^6)\) y \(\Omega(n^6)\), tenemos que es \(\Theta(n^6)\). \(\square\)
Tarea moral#
Los siguientes problemas te ayudarán a practicar lo visto en esta entrada. Para resolverlos, necesitarás usar herramientas matemáticas, computacionales o ambas.
Ordena todas las siguientes funciones de acuerdo a su comportamiento asintótico:
\[\begin{align*} &n!, 2^n, \sqrt{n}, \log \log n,\\ &3^{\sqrt{n}}, n^2, n^{3/2}, (\log n) ^{3/2},\\ &n^2\log n, n^3 (1.5)^n, n^{7/3}\log n, (n^2)!,\\ &(n!)^2, 2^{2^n}, 2^{n!}, \log(n!). \end{align*}\]Para cada una de las siguientes funciones, encuentra una función mucho más sencilla y que tenga el mismo comportamiento asintótico.
\[\begin{align*} &5n^3-2n^2+3n+7,\\ &n\log n + n^2\log (n^2) + n^3 \log(n^3),\\ &2^n+3^n+(1.5)^n+n^{100},\\ &(2^n+3n+\sqrt{n})(3n+(\log^2 n)+\sqrt{n}),\\ &n^3+2n(n\log n + 3n^2 - 8n),\\ &(n!)^2+(n^2)!+2^{n^2}+2^{2n},\\ & 1 + 2 + 3 + \ldots + n,\\ & \binom{n}{7}+\binom{n}{6}+\binom{n}{5}+\ldots+\binom{n}{0},\\ & n + (n/2) + (n/4) + (n/8) + \ldots,\\ & 1+ (1/2) + (1/3) + (1/4) + \ldots + (1/n). \end{align*}\]Demuestra que tener el mismo orden es una relación de equivalencia.
Enuncia y demuestra un truco del límite para la notación \(\Omega\) y uno para la notación \(\Theta\).
Sea \(d(n)\) la cantidad de dígitos del entero positivo \(n\). Demuestra que \(d(n)=O(\Theta(n))\).