why zpopmin time complexity is log n?

Question

from redis doc:

ZPOPMIN key [count] Available since 5.0.0.

Time complexity: O(log(N)*M) with N being the number of elements in the sorted set, and M being the number of elements popped.

Removes and returns up to count members with the lowest scores in the sorted set stored at key.

So, my question is, if the list is sorted, why it's take log n, why not O(1)?

Answer 1

If the list is sorted, why it's take log n, why not O(1)?

If sorted sets were implemented with lists, you could in fact do this in O(1) time per element. However, sorted sets are implemented (in part) with the skip list data structure, which does insertions and deletions in O(log(N)) time.

Answer 2

The time complexity of accessing any element in the Sorted Set by its score is O(log(N)), hence the command's complexity.