[SER222] Asymptotics (2/5): Upper Bounds

Summary

En este video se explica la idea de una cota superior utilizando funciones matemáticas. El presentador muestra cómo graficar funciones para entender cuándo una función es mayor que otra más allá de un punto específico, llamado x0. Se introduce la notación de Big O, que define formalmente las cotas superiores para analizar el tiempo de ejecución de algoritmos. A través de ejemplos, se explica cómo eliminar términos no dominantes y coeficientes para encontrar el Big O de una función, destacando la importancia de aproximar la cota superior lo más cercana posible a la realidad.

Takeaways

• 📊 La función g(n) parece ser una cota superior para f(n) después de un punto específico llamado x0.
• 📝 La notación f(n) = O(g(n)) indica que f(n) tiene una cota superior en términos de g(n).
• 🔢 La definición matemática de cota superior dice que |f(n)| ≤ C * |g(n)| para n > x0, donde C es una constante.
• 📈 Al graficar, g(n) siempre está por encima de f(n) después del punto de intersección x0.
• ⚖️ Para encontrar la cota superior (O grande) de una función, se eliminan los términos no dominantes y las constantes.
• ✔️ Un ejemplo: f(n) = 2n + 3 tiene O(n) ya que el término dominante es n.
• 🔍 Se puede demostrar formalmente la cota superior al encontrar un valor de C que satisfaga la relación matemática.
• ⚙️ El proceso para determinar la cota superior de una función implica simplificar los términos y aplicar la definición de O grande.
• ⏲️ El uso de constantes en las cotas superiores da flexibilidad, permitiendo ajustar la función g(n) para que sea una cota válida.
• 🔢 En términos de logaritmos, todas las funciones logarítmicas tienen la misma cota superior debido a la conversión constante de base.

Q & A

¿Qué es una cota superior en términos de funciones matemáticas?

Una cota superior es una función que siempre está por encima de otra función a partir de un cierto punto. Esto significa que, a partir de ese punto, la función g(n) es mayor o igual que f(n).

¿Cómo se denomina la notación para expresar una cota superior?

La notación utilizada para expresar una cota superior es O grande, que se escribe como f(n) = O(g(n)), lo que significa que f(n) está acotada superiormente por g(n).

¿Qué significa x0 en el contexto de la cota superior?

x0 representa el punto de intersección a partir del cual la función g(n) siempre es mayor que f(n). Es el punto a partir del cual la cota superior es válida.

¿Por qué es importante el valor constante C en la definición de cota superior?

El valor constante C permite ajustar la función g(n) para que sea mayor que f(n) en todo momento. Da flexibilidad en la definición de la cota superior al permitir escalar la función g(n).

¿Cómo se determina la cota superior de una función f(n)?

Para determinar la cota superior, se eliminan todos los términos menos el dominante y luego se elimina el coeficiente de ese término. Esto proporciona una estimación del crecimiento máximo de la función.

¿Cuál es el procedimiento para probar que una función f(n) está acotada superiormente por g(n)?

Para probar que f(n) está acotada superiormente por g(n), se demuestra que f(n) ≤ C * g(n) para un valor de constante C y para n mayor que x0. Esto implica resolver una desigualdad que muestre que la función cumple con la definición formal.

¿Qué es un término dominante en el análisis de la cota superior?

El término dominante es el término de la función que crece más rápido a medida que n aumenta. Es el término que determina el comportamiento de la función para grandes valores de n.

¿Por qué los logs en diferentes bases pueden considerarse equivalentes en términos de O grande?

Los logs en diferentes bases son equivalentes en O grande porque el cambio de base es una operación constante, y esta constante se puede absorber en la constante C de la definición de cota superior.

¿Qué papel juegan los valores absolutos en la definición formal de la cota superior?

Los valores absolutos garantizan que solo se considere el crecimiento positivo de las funciones, ya que el tiempo o las operaciones no pueden ser negativas. Aunque matemáticamente se incluyen, en la práctica no afectan mucho el análisis.

¿Qué ocurre si una función tiene más de un punto de intersección con su cota superior?

Antes del punto x0, las funciones pueden cruzarse varias veces, pero la cota superior solo se asegura a partir de x0, donde g(n) siempre es mayor o igual que f(n). Las fluctuaciones antes de x0 no afectan la cota superior.