Time Complexity: Real-time notification pattern
O(n)
0
0
Real-time notification pattern in Redis - Time & Space Complexity
Understanding Time Complexity
When using Redis for real-time notifications, it is important to understand how the time to send messages grows as more users or notifications are involved.
We want to know how the system handles more notifications and users efficiently.
Scenario Under Consideration
Analyze the time complexity of the following Redis code snippet.
# Publish a message to a channel
PUBLISH notifications_channel "New message arrived"
# Clients subscribe to the channel
SUBSCRIBE notifications_channel
# Server pushes notifications to all subscribers in real-time
This code sends a notification message to all clients subscribed to a channel instantly.
Identify Repeating Operations
In this pattern, the main repeating operation is the message delivery to each subscriber.
- Primary operation: Delivering the published message to each subscriber.
- How many times: Once per subscriber connected to the channel.
How Execution Grows With Input
The time to deliver notifications grows as the number of subscribers increases.
| Input Size (n subscribers) | Approx. Operations |
|---|---|
| 10 | 10 message deliveries |
| 100 | 100 message deliveries |
| 1000 | 1000 message deliveries |
Pattern observation: The work grows directly with the number of subscribers; more subscribers mean more message deliveries.
Final Time Complexity
Time Complexity: O(n)
This means the time to send notifications 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 receive the message, so more subscribers mean more work and longer total delivery time.
Interview Connect
Understanding how notification delivery scales helps you design systems that handle many users smoothly and shows you can think about real-world performance.
Self-Check
"What if we changed from using PUBLISH/SUBSCRIBE to storing notifications in a list for each user? How would the time complexity change?"