Lenguaje formal (símbolos O, o, Θ, Ω, ω) para clasificar tasas de crecimiento de funciones por su comportamiento límite cuando el argumento tiende a infinito o a un límite singular.

Principio

Comparar los términos dominantes descartando contribuciones de orden inferior y factores constantes para caracterizar la escala a largo plazo o en pequeño parámetro; las relaciones se definen por límites o desigualdades acotantes.

Demostración

Para f(n)=3n^2+5n y g(n)=n^2, f(n)=Θ(g(n)) porque lim sup f(n)/g(n) está acotado superior e inferiormente por constantes positivas; comparten por tanto crecimiento cuadrático.

Aplicación incorrecta

Usar Big-O para afirmar valores precisos en entradas finitas o para comparar funciones fuera del régimen límite especificado (por ejemplo, tratar O(1) como una constante específica en vez de una clase acotada).

Consecuencia

Provee una clasificación concisa basada en el orden que guía la selección de algoritmos, análisis de escalado y aproximaciones límite, suprimiendo constantes irrelevantes.

Inversión

Igualdad exacta o cotas puntuales; invertir una comparación asintótica requiere demostrar desigualdades uniformes en rango finito o fórmulas exactas en lugar de relaciones límite.

Límite

Solo cuantifica el crecimiento en el régimen límite (usualmente argumento → ∞ o parámetro → 0); no da tasas de convergencia si los límites no existen o para funciones oscilatorias sin condiciones adicionales.

Tensión semántica

Tensión con afirmaciones probabilísticas o de caso promedio: la notación asintótica describe comportamiento por orden (a menudo peor caso), no necesariamente comportamiento típico o distribuciónal salvo que se especifique.

Síntesis

La notación asintótica es una abreviatura basada en límites que clasifica funciones por su comportamiento dominante de crecimiento o decaimiento, permitiendo comparar el término de orden principal y omitiendo la estructura de órdenes inferiores.