Antecedentes
En este caso, tenemos f(x), que puede ser una función complicada de analizar debido a su naturaleza seccionada o su comportamiento irregular. Sin embargo, podemos establecer funciones que se aproximen a f(x), es decir, que muestren un comportamiento similar a largo plazo.
La cota superior se conoce como O-grande (big O) y es la más común en el análisis asintótico. Esta cota representa una función que es mayor o igual que f(x) para valores suficientemente grandes de x, permitiendo caracterizar el crecimiento máximo de f(x) de manera simplificada.
Definición de Asíntota Superior
En el análisis de algoritmos, la asíntota superior (O-grande) representa el límite superior del crecimiento de una función, es decir, indica cómo se comporta la función en su límite superior cuando el tamaño de la entrada tiende a infinito. Formalmente, decimos que una función f(n) es O(g(n)) si existen constantes positivas c y n0 tales que:
f(n) \leq c \cdot g(n)
Esto implica que f(n) no crece más rápido que c \cdot g(n) , cuando n es suficientemente grande.
Ejemplo 1
Supongamos f(n) = 3n^2 + 5n . Queremos encontrar si f(n) = O(n^2) .
Para este caso se elige c=4 debido que la constante del término dominante de f(n) es 3 y queremos encontrar otra constante que sea mayor que ésta.
- f(n) \leq 4 \cdot g(n)
- Reemplazando los términos: 3n^2 + 5n \leq 4n^2
- Restando los términos equivalentes: 5n \leq n^2
- Podemos reducir el término de n: 5 \leq n
El conjunto solución queda: [5, +\infty)
Esto implica que todo n que sea 5 hasta el infinito cumple la premisa de f(n) \leq 4 * g(n)
Y entonces f(n) \in O(n)
Ejemplo 2
Ahora vamos a probar que falle la asíntota superior. Elegiremos como g(n) = n
Si elegimos un c = 50 para utilizar una constante mucho mayor, esto queda:
f(n) \leq 50 \cdot g(n)
3n^2 + 5n \leq 50n
3n^2 \leq 45n
3n \leq 45
n \leq 15
Esto significa que el conjunto solución es: (-\infty, 15]
Esto indica que la condición no se cumple cuando n \rightarrow +\infty , por lo tanto f(n) \notin O(n)