Ik had deze vraag op de Redis-website gecrosspost, en Pieter Noordhuis gaf daar een antwoord, dat ik hier cross-post:
Dat is juist. De gesorteerde set is afhankelijk van een RNG om het aantal niveaus per knooppunt te bepalen (het is een probabilistische gegevensstructuur). Het invoegen/verwijderen van een element aan het begin van de skiplist kan O(1) zijn, terwijl de theoretische slechtste prestatie O(N) is (waarbij elk knooppunt hetzelfde niveau heeft). De geamortiseerde tijdcomplexiteit is echter O(log N) als je rekening houdt met de verdeling van de niveaus over de knooppunten.