Wikipedia enumera el algoritmo de mediana de medianas como requeridoO(1) Espacio auxiliar.

Sin embargo, en el medio del algoritmo, hacemos una llamada r, ecursiva en un subconjunto de tamañon/5 para encontrar la mediana de las medianas. Cuando esta llamada recursiva regresa, usamos la mediana devuelta de las medianas como pivote para particionar la matriz.

¿Este algoritmo no empujaO(lg n) los registros de activación en la pila de tiempo de ejecución como parte de la recursividad? Por lo que puedo ver, estas llamadas recursivas para encontrar medianas sucesivas de medianas no pueden optimizarse debido a que hacemos un trabajo adicional después de que regresan las llamadas recursivas. Por lo tanto, parece que este algoritmo requiereO(lg n) espacio auxiliar (al igual que Quicksort, que Wikipedia enumera como requeridoO(lg n) espacio auxiliar debido al espacio utilizado por la pila de tiempo de ejecución).

¿Me estoy perdiendo algo o el artículo de Wikipedia está mal?

(Nota: la llamada recursiva a la que me refiero esreturn select(list, left, left + ceil((right - left) / 5) - 1, left + (right - left)/10) en la página de Wikipedia).