Zamieściłem to pytanie na stronie Redis, a Pieter Noordhuis udzielił tam odpowiedzi, którą zamieszczam tutaj:
To jest poprawne. Posortowany zestaw opiera się na RNG w celu określenia liczby poziomów na węzeł (jest to probabilistyczna struktura danych). Wstawianie/usuwanie elementu na początku listy pomijania może być O(1), podczas gdy teoretycznie najgorsza wydajność to O(N) (z każdym węzłem mającym ten sam poziom). Jednak złożoność zamortyzowanego czasu wynosi O(log N), gdy weźmie się pod uwagę rozkład poziomów między węzłami.
