Eu havia postado essa pergunta no site Redis, e Pieter Noordhuis forneceu uma resposta lá, que estou postando aqui:

Está correto. O conjunto classificado depende de um RNG para determinar o número de níveis por nó (é uma estrutura de dados probabilística). A inserção/exclusão de um elemento no início da skiplist pode ser O(1), enquanto o desempenho teórico do pior caso é O(N) (com todos os nós tendo o mesmo nível). No entanto, a complexidade do tempo amortizado é O(log N) quando se considera a distribuição dos níveis entre os nós.