A Wikipedia lista o algoritmo de mediana de medianas como exigindoO(1) espaço auxiliar.

No entanto, no meio do algoritmo, fazemos uma chamada ecursiva r em uma sub-matriz de tamanhon/5 para encontrar a mediana das medianas. Quando essa chamada recursiva retorna, usamos a mediana retornada de medianas como um pivô para particionar a matriz.

Esse algoritmo não empurraO(lg n) registros de ativação na pilha de tempo de execução como parte da recursão? Pelo que pude ver, essas chamadas recursivas para encontrar medianas sucessivas de medianas não podem ser otimizadas para chamadas finais, porque fazemos um trabalho extra após o retorno das chamadas recursivas. Portanto, parece que esse algoritmo requerO(lg n) espaço auxiliar (como o Quicksort, que a Wikipedia lista como exigindoO(lg n) espaço auxiliar devido ao espaço usado pela pilha de tempo de execução).

Estou faltando alguma coisa ou o artigo da Wikipedia está errado?

(Nota: a chamada recursiva à qual me refiro éreturn select(list, left, left + ceil((right - left) / 5) - 1, left + (right - left)/10) na página da Wikipedia.)