Algoritmo: Es un buen definido procedimiento computacional que toma algunos valores, o un conjunto de valores, como entrada y produce algunos valores, o conjunto de valores, como salida. Así es como un algoritmo es una secunecia de pasos computacionales que transforma una entrada en una salida.
Analisis de Algoritmo: Analizar un algortimo es predecir los recursos que el algoritmo requiere. Ocacionalmente, recursos tales como memoria, ancho de banda de comunicación, o número de compuertas lóginas son de gran interés, pero más común es la cantidad de tiempo computacional la que se desea medir.
Tamaño de la entrada: Depende del problema en estudio. Puede ser
número de datos a ser ordenados, número de bits a ser multiplicados,
o el par número de nodos y arcos de un grafo.
Tiempo de ejecución: Es el número de operaciones primitivas
o "pasos" ejecutados.
Ejemplo:
Consideremos el algoritmo "insertion-sort"
| Algoritmo | Costo | Veces |
| InsertionSort(int A[], int n) { | c1 | 1 |
| int j, i, key; | c2 | 1 |
| for (j=1; j<n; j++) { | c3 | n-1 |
| key = A[j]; | c4 | n-1 |
| i = j-1; | c5 | n-1 |
| while( i>=0 && A[i] > key ) { | c6 | Suma desde j=1 hasta n-1 de tj |
| A[i+1] = A[i]; | c7 | Suma desde j=1 hasta n-1 de (tj - 1) |
| i --; | c8 | Suma desde j=1 hasta n-1 de (tj -1) |
| } | 0 | - |
| A[i+1]=key; | c9 | n-1 |
| } | 0 | - |
| } | 0 | - |