XRANGE and XREVRANGE in Redis - Time & Space Complexity

Time Complexity: XRANGE and XREVRANGE

O(n)

Understanding Time Complexity

When working with Redis streams, it's important to know how the time to get data grows as the stream gets bigger.

We want to understand how fast XRANGE and XREVRANGE commands run when we ask for entries.

Scenario Under Consideration

Analyze the time complexity of the following Redis commands.

# Get entries from a stream in forward order
XRANGE mystream - + COUNT 100

# Get entries from a stream in reverse order
XREVRANGE mystream + - COUNT 100
    

These commands fetch up to 100 entries from the stream named 'mystream', either from oldest to newest or newest to oldest.

Identify Repeating Operations

Look at what repeats when these commands run.

• Primary operation: Scanning entries in the stream to find requested range.
• How many times: Up to the number of entries requested (COUNT), or until the range ends.

How Execution Grows With Input

As you ask for more entries, the work grows roughly in direct proportion.

Input Size (n)	Approx. Operations
10	About 10 steps to get entries
100	About 100 steps
1000	About 1000 steps

Pattern observation: The time grows linearly with the number of entries requested.

Final Time Complexity

Time Complexity: O(n)

This means the time to get entries grows directly with how many entries you ask for.

Common Mistake

[X] Wrong: "XRANGE and XREVRANGE always take the same time no matter how many entries are requested."

[OK] Correct: The commands scan through entries to return results, so asking for more entries takes more time.

Interview Connect

Understanding how XRANGE and XREVRANGE scale helps you explain how to efficiently read data from streams in real projects.

Self-Check

"What if we remove the COUNT option and request the entire stream? How would the time complexity change?"