Time Complexity es un concepto en informática que se ocupa de la cuantificación de la cantidad de tiempo que tarda un conjunto de código o algoritmo en procesarse o ejecutarse en función de la cantidad de entrada. En otras palabras, la complejidad del tiempo es cuánto tarda un programa en procesar una entrada determinada. La eficiencia de un algoritmo depende de dos parámetros:
- Complejidad del tiempo
- Complejidad espacial
Complejidad de tiempo: se define como el número de veces que se ejecuta un conjunto de instrucciones en particular en lugar del tiempo total que se toma. Es porque el tiempo total que tomó también depende de algunos factores externos como el compilador utilizado, la velocidad del procesador, etc.
Complejidad espacial: Es el espacio total de memoria que requiere el programa para su ejecución.
Complejidad de tiempo en el mejor de los casos de diferentes estructuras de datos para diferentes operaciones
| Estructura de datos | Acceso | Búsqueda | Inserción | Supresión |
| Formación | O(1) | O(1) | O(1) | O(1) |
| Pila | O(1) | O(1) | O(1) | O(1) |
| Cola | O(1) | O(1) | O(1) | O(1) |
| Lista de enlaces individuales | O(1) | O(1) | O(1) | O(1) |
| Lista doblemente enlazada | O(1) | O(1) | O(1) | O(1) |
| Tabla de picadillo | O(1) | O(1) | O(1) | O(1) |
| Árbol de búsqueda binaria | O (registro n) | O (registro n) | O (registro n) | O (registro n) |
| Árbol AVL | O (registro n) | O (registro n) | O (registro n) | O (registro n) |
| Árbol B | O (registro n) | O (registro n) | O (registro n) | O (registro n) |
| Árbol negro rojo | O (registro n) | O (registro n) | O (registro n) | O (registro n) |
Complejidad temporal en el peor de los casos de diferentes estructuras de datos para diferentes operaciones
| Estructura de datos | Acceso | Búsqueda | Inserción | Supresión |
| Formación | O(1) | EN) | EN) | EN) |
| Pila | EN) | EN) | O(1) | O(1) |
| Cola | EN) | EN) | O(1) | O(1) |
| Lista de enlaces individuales | EN) | EN) | O(1) | O(1) |
| Lista doblemente enlazada | EN) | EN) | O(1) | O(1) |
| Tabla de picadillo | EN) | EN) | EN) | EN) |
| Árbol de búsqueda binaria | EN) | EN) | EN) | EN) |
| Árbol AVL | O (registro N) | O (registro N) | O (registro N) | O (registro N) |
| Árbol binario | EN) | EN) | EN) | EN) |
| Árbol negro rojo | O (registro N) | O (registro N) | O (registro N) | O (registro N) |
Complejidad de tiempo promedio de diferentes estructuras de datos para diferentes operaciones
| Estructura de datos | Acceso | Búsqueda | Inserción | Supresión |
| Formación | O(1) | EN) | EN) | EN) |
| Pila | EN) | EN) | O(1) | O(1) |
| Cola | EN) | EN) | O(1) | O(1) |
| Lista de enlaces individuales | EN) | EN) | O(1) | O(1) |
| Lista doblemente enlazada | EN) | EN) | O(1) | O(1) |
| Tabla de picadillo | O(1) | O(1) | O(1) | O(1) |
| Árbol de búsqueda binaria | O (registro N) | O (registro N) | O (registro N) | O (registro N) |
| Árbol AVL | O (registro N) | O (registro N) | O (registro N) | O (registro N) |
| Árbol B | O (registro N) | O (registro N) | O (registro N) | O (registro N) |
| Árbol negro rojo | O (registro N) | O (registro N) | O (registro N) | O (registro N) |