According to https://redis.io/commands/zpopmin, the time complexity of ZPOPMIN is O(log(N)*M).
However, given the following description:
Removes and returns up to count members with the lowest scores in the sorted set stored at key.
I would have expected something more along the lines of O(M), particularly given that the set is a sorted one and we're popping values starting from one end of it.
Why is the size of the set itself a factor in the time complexity of ZPOPMIN?
On a separate note, given that I use it on a daily basis, I'll just take this chance to say thank you for the amazing piece of software that Redis is.
Comment From: itamarhaber
Hello @jacoscaz - thank you for using Redis, it is indeed an amazing project :)
Why is the size of the set itself a factor in the time complexity of ZPOPMIN?
A Sorted Set is implemented internally with a hashtable and a skip list. Searching a skip list is on average O(log(N)), regardless of value.
Comment From: jacoscaz
Ah, fair enough. Thank you for clarifying @itamarhaber !