Time Complexity: WebSockets for real-time communication
O(n)
0
0
WebSockets for real-time communication in Computer Networks - Time & Space Complexity
Understanding Time Complexity
When using WebSockets for real-time communication, it is important to understand how the time taken to send and receive messages changes as more messages or users are involved.
We want to know how the system handles increasing communication load efficiently.
Scenario Under Consideration
Analyze the time complexity of this simplified WebSocket server handling messages.
// Pseudocode for WebSocket message broadcast
function onMessageReceived(message) {
for (let client of connectedClients) {
client.send(message);
}
}
This code sends a received message to all connected clients, broadcasting it in real-time.
Identify Repeating Operations
Look at what repeats when a message arrives.
- Primary operation: Sending the message to each connected client.
- How many times: Once for every client connected to the server.
How Execution Grows With Input
As the number of clients grows, the number of send operations grows too.
| Input Size (n) | Approx. Operations |
|---|---|
| 10 clients | 10 sends |
| 100 clients | 100 sends |
| 1000 clients | 1000 sends |
Pattern observation: The work grows directly with the number of clients; doubling clients doubles the work.
Final Time Complexity
Time Complexity: O(n)
This means the time to broadcast a message grows linearly with the number of connected clients.
Common Mistake
[X] Wrong: "Sending a message to all clients takes the same time no matter how many clients there are."
[OK] Correct: Each client needs its own send operation, so more clients mean more work and more time.
Interview Connect
Understanding how message broadcasting scales helps you design systems that handle many users smoothly, a key skill in real-time communication roles.
Self-Check
What if the server only sent messages to a fixed number of clients instead of all? How would the time complexity change?