Zveřejnil jsem tuto otázku na webu Redis a Pieter Noordhuis tam poskytl odpověď, kterou posílám zde:
To je správně. Seřazená sada se spoléhá na RNG k určení počtu úrovní na uzel (je to pravděpodobnostní datová struktura). Vložení/vymazání prvku na začátek skiplistu může být O(1), zatímco teoretický výkon v nejhorším případě je O(N) (s každým uzlem má stejnou úroveň). Nicméně amortizovaná časová složitost je O(log N), když vezmete v úvahu rozložení úrovní mezi uzly.