Había publicado esta pregunta en el sitio web de Redis y Pieter Noordhuis proporcionó una respuesta allí, que estoy publicando aquí:
Eso es correcto. El conjunto ordenado se basa en un RNG para determinar el número de niveles por nodo (es una estructura de datos probabilística). Insertar/borrar un elemento al comienzo de la lista de saltos puede ser O(1), mientras que el rendimiento teórico en el peor de los casos es O(N) (con todos los nodos con el mismo nivel). Sin embargo, la complejidad del tiempo amortizado es O(log N) cuando se tiene en cuenta la distribución de los niveles entre los nodos.
