El análisis de la eficiencia algorítmica nos lleva a estudiar el comportamiento de los algoritmos frente a condiciones extremas. Matemáticamente hablando, cuando N tiende al infinito, es un comportamiento asintótico.

Así pues, sean g(n) diferentes funciones que determinan el uso de recursos, pudiendo existir infinidad de funciones g. Estas funciones serán congregadas en familias, usando como criterio de agrupación su comportamiento asintótico.

Una familia de funciones que comparten un mismo comportamiento asintótico será llamada un Orden de Complejidad. Estas familias se designan con O().

Para cada uno de estos conjuntos se suele identificar un miembro f(n) que se utiliza como representante de la familia, hablándose del conjunto de funciones g que son del orden de f(n), denotándose como:

g O(f(n)), g está incluido en f(n)

Frecuentemente no es necesario conocer el comportamiento exacto, basta conocer una cota superior, es decir, alguna función que se comporte "aún peor".

El conjunto O(f(n)) está formado por aquellas funciones g(n) que crecen a un ritmo menor o igual que el de f(n).

El conjunto Ω(f(n)) está formado por aquellas funciones g(n) que crecen a un ritmo mayor o igual que el de f(n).

El conjunto Θ(f(n)) está formado por aquellas funciones g(n) que crecen exactamente al mismo ritmo que el de f(n).

De las funciones g que forman el conjunto O(f(n)) se dice que están dominadas asintóticamente por f, en el sentido de que para N suficientemente grande, y salvo una constante multiplicativa k, f(n) es una cota superior de g(n).

Debemos tomar en cuenta, que el orden de un algoritmo depende del grado máximo del polinomio que define a la función.

La notación O() ignora los factores constantes, desconoce si se hace una mejor o peor implementación del algoritmo, además de ser independiente de los datos de entrada del algoritmo. Es decir, la utilidad de aplicar esta notación a un algoritmo es encontrar el límite superior de su tiempo de ejecución "el peor caso".