Complejidad Bonus

[antoniablanco]

En el bonus se pide un peor caso de O(log(n)), pero esto no es posible si la consulta lleva a imprimir a todas las cabezas. Por ejemplo en la búsqueda por circulo, si el círculo contiene a todos los elementos del árbol si o si se tendrá que pasar por todo el árbol lo que es O(n). Quería preguntar si es que se evitará entregar este tipo de casos, por que si no, creo que es imposible cumplirlo.
Saludos!

[benjavicente]

Del form:

Es la complejidad de búsqueda, no considera la complejidad adicional que existe dado la cantidad de resultados.

Se trata de expresar que $O(log(n))$ sea la complejidad de búsqueda que se emplea en la EDD. Como dices, está restringido a iterar los $k$ resultados, entonces realmente es $O(log(n) + k)$ el límite. Y si vas aún más en detalle, hay complejidades como $O(log(n) + m + k)$, $O(log^2(n) + k)$ o $O(log(n) +klog(k))$ que salen de algoritmos que emplean búsqueda basada en áboles, de $O(log(n))$, y no llegan al límite de $O(log(n) + k)$.

Al final, no podemos poner como una complejidad máxima precisa porque las técnicas varían mucho. Pero pedimos ahí en el formulario que las EDDs que se componen para realizar la búsqueda, tengan complejidad de búsqueda $O(log(n))$ (en el peor caso vs el promedio en el enunciado 👀) , que hagan que el algoritmo final no sea $O(n)$ en el peor caso (sin considerar cantidad de resultados).

PD: lo trate de aclarar ahora mejor en el form