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))

Practice

1. What does the Redis command ZRANGE myset 0 2 do?

easy

A. Deletes the first three elements from the sorted set 'myset'.

B. Returns the first three elements with the lowest scores from the sorted set 'myset'.

C. Returns the last three elements with the highest scores from the sorted set 'myset'.

D. Returns all elements from the sorted set 'myset' without any order.

Solution

1. Step 1: Understand ZRANGE command behavior

   ZRANGE returns elements in ascending order by score, from the start index to the end index.

2. Step 2: Apply the index range 0 to 2

   Indexes 0 to 2 mean the first three elements with the lowest scores are returned.

3. Final Answer:

   Returns the first three elements with the lowest scores from the sorted set 'myset'. -> Option B

4. Quick Check:

   ZRANGE with 0 2 = first 3 lowest scored items [OK]

Hint: ZRANGE gets items low to high by index range [OK]

Common Mistakes:

• Confusing ZRANGE with ZREVRANGE order
• Thinking it deletes elements
• Assuming it returns all elements unordered

2. Which of the following is the correct syntax to get the top 5 highest scored elements from a sorted set named 'scores'?

easy

A. ZREVRANGE scores 0 4

B. ZRANGE scores -5 -1

C. ZRANGE scores 0 4 WITHSCORES

D. ZREVRANGE scores 5 0

Solution

1. Step 1: Identify command for highest scores first

   ZREVRANGE returns elements from highest to lowest score.

2. Step 2: Use index range 0 to 4 for top 5 elements

   Indexes 0 to 4 select the first 5 elements in descending order.

3. Final Answer:

   ZREVRANGE scores 0 4 -> Option A

4. Quick Check:

   Top 5 highest = ZREVRANGE 0 4 [OK]

Hint: Use ZREVRANGE 0 N-1 for top N highest scores [OK]

Common Mistakes:

• Using negative indexes incorrectly with ZRANGE
• Confusing ZRANGE and ZREVRANGE
• Wrong index order like 5 0

3. Given a sorted set 'players' with elements and scores: {"Alice":10, "Bob":20, "Carol":15}, what is the output of ZRANGE players 0 1 WITHSCORES?

medium

A. ["Bob", "20", "Carol", "15"]

B. ["Alice", "10", "Bob", "20"]

C. ["Carol", "15", "Bob", "20"]

D. ["Alice", "10", "Carol", "15"]

Solution

1. Step 1: Sort elements by score ascending

   Sorted order by score: Alice(10), Carol(15), Bob(20).

2. Step 2: Select indexes 0 to 1 with scores

   Indexes 0 and 1 correspond to Alice and Carol with their scores.

3. Final Answer:

   ["Alice", "10", "Carol", "15"] -> Option D

4. Quick Check:

   ZRANGE 0 1 WITHSCORES = Alice and Carol with scores [OK]

Hint: ZRANGE returns low to high; WITHSCORES adds scores after each element [OK]

Common Mistakes:

• Mixing order of elements
• Forgetting WITHSCORES doubles output
• Assuming ZREVRANGE order

4. You run ZREVRANGE leaderboard 0 2 but get unexpected results. Which of these is a likely cause?

medium

A. ZREVRANGE does not support index ranges.

B. You used ZRANGE instead of ZREVRANGE.

C. The sorted set 'leaderboard' is empty or does not exist.

D. The index range 0 2 is invalid for ZREVRANGE.

Solution

1. Step 1: Check if sorted set exists and has elements

   If 'leaderboard' is empty or missing, ZREVRANGE returns empty result.

2. Step 2: Validate command and index usage

   ZREVRANGE supports index ranges; 0 2 is valid; using ZRANGE instead would change order but not cause empty result.

3. Final Answer:

   The sorted set 'leaderboard' is empty or does not exist. -> Option C

4. Quick Check:

   Empty set causes empty ZREVRANGE output [OK]

Hint: Empty or missing set returns empty list [OK]

Common Mistakes:

• Thinking index range is invalid
• Confusing ZRANGE and ZREVRANGE effects
• Believing ZREVRANGE lacks index support

5. You want to get the middle 3 elements by score from a sorted set 'scores' with 10 elements, ordered from lowest to highest. Which command correctly retrieves elements ranked 4th to 6th (0-based index) with their scores?

hard

A. ZRANGE scores 3 5 WITHSCORES

B. ZREVRANGE scores 3 5 WITHSCORES

C. ZRANGE scores 4 6 WITHSCORES

D. ZREVRANGE scores 4 6 WITHSCORES

Solution

1. Step 1: Identify index range for middle 3 elements

   Elements ranked 4th to 6th correspond to indexes 3, 4, 5 (0-based).

2. Step 2: Use ZRANGE for ascending order and WITHSCORES to get scores

   ZRANGE scores 3 5 WITHSCORES returns elements at indexes 3 to 5 with their scores.

3. Final Answer:

   ZRANGE scores 3 5 WITHSCORES -> Option A

4. Quick Check:

   Middle 3 elements = ZRANGE 3 5 WITHSCORES [OK]

Hint: ZRANGE with correct indexes gets middle elements low to high [OK]

Common Mistakes:

• Using ZREVRANGE which reverses order
• Off-by-one errors in index range
• Confusing rank with index