Redis:ZADD по-добър ли е от O(logN), когато вмъкнатият елемент е в началото или в края?

Бях публикувал кръстосано този въпрос на уебсайта Redis и Pieter Noordhuis предостави отговор там, който публикувам кръстосано тук:

Това е вярно. Сортираният набор разчита на RNG, за да определи броя на нивата на възел (това е вероятностна структура от данни). Вмъкването/изтриването на елемент в началото на списъка за прескачане може да бъде O(1), докато теоретичната производителност в най-лошия случай е O(N) (като всеки възел има същото ниво). Въпреки това, амортизираната времева сложност е O(log N), когато вземете предвид разпределението на нивата между възлите.