Complejidad interna y externa

Una vez que hemos determinado la relación de equivalencia a usar (por ejemplo los pivotes), procesamos el conjunto pero guardando para cada elemento de $U$, sus coordenadas (es decir la distancia a los pivotes). Esto toma $O(Pn)$ tiempo de preprocesamiento y espacio en memoria principal. El índice puede ser visto como una tabla de $n$ renglones y columnas como se muestra en la parte izquierda de la figura .

En tiempo de consulta, primero comparamos la consulta $q$ contra los pivotes, entonces obtenemos sus coordenadas $(y_1,...y_P)$ en el espacio. Esto corresponde a determinar cuales clases equivalentes pertenecen a la consulta. El costo de estas evaluaciones de la función de distancia $d$, corresponden a la complejidad interna de la búsqueda. Ahora tenemos que determinar, en el espacio, cuales clases pueden ser relevantes a la consulta (por ejemplo cuales están a distancia $r$ o menos) recorriendo el índice, esto puede tomar un costo extra de CPU. Finalmente, los elementos en las clases calificadas (aquellos que no pudieron ser descartados después de considerar los pivotes) son directamente comparados contra $q$ (complejidad externa). La complejidad interna y externa son usadas para comparar el desempeño de un algoritmo.

Figura: Vista esquemática de un índice usando pivotes, así como un recorrido horizontal y vertical