Cota ajustada asintótica

En análisis de algoritmos una cota ajustada asintótica es una función que sirve de cota tanto superior como inferior de otra función cuando el argumento tiende a infinito. Usualmente se utiliza la notación Θ(g(x)) para referirse a las funciones acotadas por la función g(x).

Más formalmente se define:

Ejemplos

  • La función f(x) = x+10 puede ser acotada por la función g(x) = x. Para demostrarlo basta notar que para todo valor de x≥1 se cumple que g(x)≤f(x)≤11g(x), es decir x ≤ x+10 ≤ 11x . Por lo tanto x+10 = Θ(x).
Other Languages