Time Complexity: Retained messages
O(n)
0
0
Retained messages in IOT Protocols - Time & Space Complexity
Understanding Time Complexity
When devices use retained messages, the broker stores the last message on a topic. We want to understand how the time to handle these messages changes as more topics have retained messages.
How does the broker's work grow when sending retained messages to new subscribers?
Scenario Under Consideration
Analyze the time complexity of the following code snippet.
// When a new client subscribes:
for each topic in subscribed_topics {
if (topic has retained_message) {
send retained_message to client;
}
}
This code sends all retained messages for the topics a client subscribes to, right after subscription.
Identify Repeating Operations
Identify the loops, recursion, array traversals that repeat.
- Primary operation: Looping over all subscribed topics to check for retained messages.
- How many times: Once per topic the client subscribes to.
How Execution Grows With Input
As the number of subscribed topics grows, the broker must check and send more retained messages.
| Input Size (n) | Approx. Operations |
|---|---|
| 10 | 10 checks and possible sends |
| 100 | 100 checks and possible sends |
| 1000 | 1000 checks and possible sends |
Pattern observation: The work grows directly with the number of subscribed topics.
Final Time Complexity
Time Complexity: O(n)
This means the time to send retained messages grows linearly with the number of topics subscribed.
Common Mistake
[X] Wrong: "Sending retained messages happens instantly no matter how many topics there are."
[OK] Correct: Each topic with a retained message requires a separate send operation, so more topics mean more work and time.
Interview Connect
Understanding how retained messages affect broker performance shows you can think about real-world system scaling. This skill helps you design efficient IoT solutions.
Self-Check
"What if the broker cached retained messages and sent them in batches? How would the time complexity change?"