Time Complexity: Pub/sub limitations (no persistence)
O(n)
0
0
Pub/sub limitations (no persistence) in Redis - Time & Space Complexity
Understanding Time Complexity
When using Redis Pub/Sub, messages are sent to subscribers instantly without saving them.
We want to understand how the time to deliver messages grows as more subscribers join.
Scenario Under Consideration
Analyze the time complexity of this Redis Pub/Sub publish operation.
# Subscribe clients to a channel
SUBSCRIBE channel1
# Publish a message to all subscribers
PUBLISH channel1 "Hello subscribers!"
This code sends a message to all clients subscribed to channel1 immediately without storing it.
Identify Repeating Operations
Look for repeated actions in the publish process.
- Primary operation: Sending the message to each subscriber.
- How many times: Once for each subscriber connected to the channel.
How Execution Grows With Input
As the number of subscribers grows, the work to send messages grows too.
| Input Size (n) | Approx. Operations |
|---|---|
| 10 subscribers | 10 sends |
| 100 subscribers | 100 sends |
| 1000 subscribers | 1000 sends |
Pattern observation: The number of sends grows directly with the number of subscribers.
Final Time Complexity
Time Complexity: O(n)
This means the time to deliver a message grows linearly with the number of subscribers.
Common Mistake
[X] Wrong: "Publishing a message takes the same time no matter how many subscribers there are."
[OK] Correct: Each subscriber must get the message separately, so more subscribers mean more work.
Interview Connect
Understanding how message delivery time grows helps you design systems that handle many users efficiently.
Self-Check
"What if Redis stored messages for offline subscribers? How would that change the time complexity of publishing?"