Algoritmos y Estructuras de Datos (VJ1215)

Coste temporal en el peor caso: O(n).

Coste temporal en el mejor caso: O(1).

Coste espacial en el peor caso: O(n).

Coste espacial en el mejor caso: O(n).

El coste temporal en el peor caso se da cuando el dato buscado no se encuentra en el vector. El coste temporal en el mejor caso se da cuando el dato se encuentra al final del vector.

En el coste espacial se incluyen tanto el coste del vector como el coste de la pila de llamadas. El coste del vector es O(n) al haber un único vector compartido por todas las llamadas, porque se pasa por referencia a todas. El coste de la pila de llamadas no supera eso, porque a lo sumo hay O(n) llamadas activas simultáneamente y el espacio ocupado por cada una en la pila de llamadas es O(1).