O(S+N) where S is the distance of start offset from HEAD for small lists, from nearest end (HEAD or TAIL) for large lists; and N is the number of elements in the specified range.
According to https://github.com/redis/redis-doc/pull/331, this only applies to List based on ziplist and linkedlist. For List based on quicklist, the complexity should be O(S+N), S is the distance of start offset from HEAD in redis 4.0 to 6.0 version, from nearest end (HEAD or TAIL) in redis 7.0 according to https://github.com/redis/redis/pull/9454 ?
Comment From: itamarhaber
Sounds O(K) to me ;)
Moving this to the mothership repo as any fixes would go into 'src/commands/lrange.json'.