ZRANGE and ZREVRANGE for reading in Redis - Time & Space Complexity

Time Complexity: ZRANGE and ZREVRANGE for reading

O(log(N)+M)

Understanding Time Complexity

When we use ZRANGE or ZREVRANGE commands in Redis, we want to know how the time it takes changes as the size of the sorted set grows.

We ask: How does reading a range of elements from a sorted set scale with its size?

Scenario Under Consideration

Analyze the time complexity of the following Redis commands.

# Get elements from index 0 to 9 in ascending order
ZRANGE mysortedset 0 9

# Get elements from index 0 to 9 in descending order
ZREVRANGE mysortedset 0 9
    

These commands read a slice of 10 elements from a sorted set, either from smallest to largest or largest to smallest.

Identify Repeating Operations

Look at what repeats when Redis executes these commands.

• Primary operation: Redis navigates to the starting index using the skip list structure in O(log N) time, then collects the requested range of M elements.
• How many times: O(log N + M) where N is the sorted set size and M is the number of elements requested.

How Execution Grows With Input

Imagine the sorted set has many elements, but you only ask for a small slice.

Input Size (N)	Approx. Operations (M=10)
10	About log(10)+10 ≈ 13 operations
100	About log(100)+10 ≈ 17 operations
1000	About log(1000)+10 ≈ 20 operations

Pattern observation: The time grows logarithmically with N and linearly with M. For fixed small M, it is nearly independent of N.

Final Time Complexity

Time Complexity: O(log(N)+M)

This means the time grows linearly with the number of elements you ask to read (M) and logarithmically with the total size of the sorted set (N).

Common Mistake

[X] Wrong: "Reading a range from a large sorted set takes time proportional to the whole set size O(N)."

[OK] Correct: Redis uses skip lists to find the range start in O(log N) time and only processes the requested M elements.

Interview Connect

Understanding how Redis commands scale helps you design fast data access patterns and answer questions confidently about performance.

Self-Check

What if we asked for the entire sorted set instead of a small range (e.g., ZRANGE mysortedset 0 -1)? How would the time complexity change? (O(log(N)+N) = O(N))