WebSocket transport in GraphQL - Time & Space Complexity

Time Complexity: WebSocket transport

O(n)

Understanding Time Complexity

When using WebSocket transport in GraphQL, we want to understand how the time to handle messages grows as more data or clients connect.

We ask: How does the work increase when more messages or subscriptions happen?

Scenario Under Consideration

Analyze the time complexity of the following GraphQL subscription over WebSocket.

subscription OnMessageReceived {
  messageReceived {
    id
    content
    sender
  }
}
    

This subscription listens for new messages sent to the server and pushes them to clients over WebSocket.

Identify Repeating Operations

Look for repeated actions that affect time.

• Primary operation: Sending each new message to all subscribed clients.
• How many times: Once per message, repeated for each client subscribed.

How Execution Grows With Input

As the number of clients or messages grows, the work grows too.

Input Size (n = clients)	Approx. Operations (sending messages)
10	10 sends per message
100	100 sends per message
1000	1000 sends per message

Pattern observation: The work grows linearly with the number of subscribed clients.

Final Time Complexity

Time Complexity: O(n)

This means the time to send messages grows directly with the number of clients connected.

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 message sent, so more clients mean more work.

Interview Connect

Understanding how WebSocket message delivery scales helps you explain real-time data flow in apps clearly and confidently.

Self-Check

What if the server batches messages before sending? How would that affect the time complexity?