Jag hade korspostat den här frågan på Redis webbplats, och Pieter Noordhuis gav ett svar där, som jag korsinlägger här:
Det är korrekt. Den sorterade uppsättningen förlitar sig på en RNG för att bestämma antalet nivåer per nod (det är en probabilistisk datastruktur). Att infoga/ta bort ett element i början av överhoppningslistan kan vara O(1), medan det teoretiska värsta fallet är O(N) (med varje nod som har samma nivå). Den amorterade tidskomplexiteten är dock O(log N) när man tar hänsyn till fördelningen av nivåerna mellan noderna.