Una vez que obtengamos un algoritmo que funcione correctamente, es importante conocer cual es el rendimiento del mismo. De esta forma, cuando se nos presente un problema a resolver y tengamos diversos algoritmos a nuestra disposición, sabremos cual es el ideal dadas las circunstancias.

Existen muchas variables que podemos medir para determinar el rendimiento, pero las dos más importantes son: el tiempo y el tamaño en memoria. De estos dos recursos, el tiempo es muchas veces el más importante y el más difícil de estimar. Para calcular el tamaño, si no utilizamos recursividad o memoria dinámica, basta con ver la cantidad de memoria que ocuparían las variables de acuerdo a la entrada que se nos presente.

El primer problema con el que nos atravesamos al estimar el tiempo de ejecución de un algoritmo es que la duración que tarda en ejecutarse un programa varía de acuerdo a la entrada que ingresemos. En ocasiones, para entradas del mismo tamaño, el algoritmo tarda tiempos distintos. No obstante, es común que entre más crezca la entrada, más se tarde la ejecución. Es por esto que el tiempo de ejecución lo vamos a definir en función del tamaño de la entrada.

Otro inconveniente que tenemos es escoger la forma de medición que utilizaremos. Los primero que podemos intentar es cronometrar el tiempo que toman varias entradas en correr y hacer estimaciones en base a esto. Nos topamos, sin embargo, con que al realizar las mismas pruebas en otra computadora los resultados pueden cambiar significativamente.

Por esto, el tiempo de ejecución de un algoritmo lo definimos por el número de instrucciones u operaciones ejecutadas. Una línea de código puede correr en diferente tiempo que otra (realizar una multiplicación normalmente tarda más que una suma), pero en general vamos a suponer que la ejecución de cualquier instrucción básica tarda lo mismo.

La última contrariedad que afrontamos es la implementación del algoritmo. Está claro que diferentes implementaciones de un mismo algoritmo van a llevarse tiempos distintos en resolver una misma entrada. Para no preocuparnos por esto, recurrimos al Principio de la Invarianza. Este principio nos indica que el tiempo de ejecución de dos implementaciones distintas de un algoritmo dado no va a diferir más que en una constante multiplicativa.