Como podemos determinar la complejidad de un algoritmo

Tiempo de Ejecución

El tiempo de Ejecución de un programa se mide en función de N, lo que designaremos como T(N).
Esta función se puede calcular físicamente ejecutando el programa acompañados de un reloj, o calcularse directamente sobre el código, contando las instrucciones a ser ejecutadas y multiplicando por el tiempo requerido por cada instrucción. Así, un trozo sencillo de código como:

S1;
for(x = 0; x < N; x++)
S2;
Demanda: T(N) = t1 + t2 * N
Donde t1 es el tiempo que lleva ejecutar la serie S1 de sentencias, y t2 es el que lleva la serie S2.
Habitualmente todos los algoritmos contienen alguna sentencia condicional o selectiva, haciendo que las sentencias ejecutadas dependan de la condición lógica, esto hace que aparezca más de un valor para T(N), es por ello que debemos hablar de un rango de valores:
Tmin(N) ≤ T(N) ≤ Tmax(N)
Estos extremos son llamados "el peor caso" y "el mejor caso" y entre ambos se puede hallar "el caso promedio" o el más frecuente, siendo este el más difícil de estudiar; nos centraremos en el "el peor caso" por ser de fácil cálculo y se acerca a "el caso promedio", brindándonos una medida pesimista pero fiable.
Toda función T(N) encierra referencias al parámetro N, y a una serie de constantes Ti dependientes de factores externos al algoritmo. Se tratará de analizar los algoritmos dándoles autonomía frente a estos factores externos, buscando estimaciones generales ampliamente válidas, a pesar de ser demostraciones teóricas.