XADD for adding entries in Redis - Time & Space Complexity

Time Complexity: XADD for adding entries

O(1)

Understanding Time Complexity

When we add entries to a Redis stream using XADD, it's important to know how the time it takes grows as the stream gets bigger.

We want to understand how the cost of adding one entry changes when the stream has more data.

Scenario Under Consideration

Analyze the time complexity of the following Redis command.

XADD mystream * sensor-id 1234 temperature 19.8
    

This command adds a new entry with fields like sensor-id and temperature to the stream named 'mystream'.

Identify Repeating Operations

Look for any repeated steps inside the XADD operation.

• Primary operation: Inserting the new entry at the end of the stream.
• How many times: This happens once per XADD call; no loops inside the command itself.

How Execution Grows With Input

Adding one entry takes about the same time no matter how many entries are already in the stream.

Input Size (entries in stream)	Approx. Operations
10	Constant time steps
100	Constant time steps
1000	Constant time steps

Pattern observation: The time to add one entry stays roughly the same even as the stream grows larger.

Final Time Complexity

Time Complexity: O(1)

This means adding an entry takes about the same amount of time no matter how many entries are already in the stream.

Common Mistake

[X] Wrong: "Adding entries gets slower as the stream grows because Redis has to look through all previous entries."

[OK] Correct: Redis streams are designed to append entries efficiently, so adding one entry does not require scanning the whole stream.

Interview Connect

Understanding that XADD runs in constant time helps you explain how Redis handles data efficiently, a useful skill when discussing real-time data systems.

Self-Check

"What if we added multiple entries at once using XADD in a pipeline? How would that affect the overall time complexity?"