La familia O(f(n)) representa un Orden de Complejidad de donde f(n) es la función más sencilla de la familia.

Las funciones de complejidad algorítmica más habituales en las cuales el único factor del que dependen es el tamaño de la muestra de entrada n, ordenadas de mayor a menor eficiencia son:

Se identifica una Jerarquía de Ordenes de Complejidad en el sentido de que cada orden de complejidad inferior tiene a las superiores como subconjuntos.

• O(1): Complejidad constante. Cuando las instrucciones se ejecutan una vez.

• O(log n): Complejidad logarítmica. Esta suele aparecer en determinados algoritmos con iteración o recursión no estructural, por ejemplo, la búsqueda binaria.

• O(n): Complejidad lineal. Aparece en la evaluación de bucles simples siempre que la complejidad de las instrucciones interiores sea constante.

• O(n log n): Complejidad cuasi-lineal. Se encuentra en algoritmos de tipo divide y vencerás como por ejemplo en el método de ordenación quicksort y se considera una buena complejidad. Si n se duplica, el tiempo de ejecución es ligeramente mayor del doble.

• O(n^2): Complejidad cuadrática. Aparece en bucles o ciclos doblemente anidados. Si n se duplica, el tiempo de ejecución aumenta cuatro veces.

• O(n^3): Complejidad cúbica. Suele darse en bucles con triple anidación. Si n se duplica, el tiempo de ejecución se multiplica por ocho. Para un valor grande de n empieza a crecer dramáticamente.

• O(n^a): Complejidad polinómica (a > 3). Si a crece, la complejidad del programa es bastante mala.

• O(2^n): Complejidad exponencial. No suelen ser muy útiles en la práctica por el elevadísimo tiempo de ejecución. Se dan en subprogramas recursivos que contengan dos o más llamadas internas.

Algoritmos Polinomiales: Aquellos que son proporcionales a n^a. Son en general factibles o aplicables, los problemas basados en estos algoritmos son solucionares.

Algoritmos Exponenciales: En general no son factibles salvo un tamaño de entrada n exageradamente pequeño, pero generalmente pertenecen a un universo de problemas de los cuales el cómputo se hace imposible.

Reglas de la Notación Asintótica

1. Regla de la suma

Si T1(n) y T2(n) son las funciones que expresan los tiempos de ejecución de dos fragmentos de un programa, y se acotan de forma que se tiene:

y

Se puede decir que:

2. Regla del producto

Si T1(n) y T2(n) son las funciones que expresan los tiempos de ejecución de dos fragmentos de un programa, y se acotan de forma que se tiene:

y

Se puede decir que: