MQTT keep-alive and timeout in IOT Protocols - Time & Space Complexity

Time Complexity: MQTT keep-alive and timeout

O(n)

Understanding Time Complexity

We want to understand how the MQTT client checks for keep-alive messages and handles timeouts as the number of messages grows.

How does the time spent checking change when more messages or connections are involved?

Scenario Under Consideration

Analyze the time complexity of the following MQTT keep-alive check code.

function checkKeepAlive(clients) {
  for (let client of clients) {
    if (currentTime - client.lastMessageTime > client.keepAliveInterval) {
      disconnect(client);
    }
  }
}

This code loops through all connected clients and disconnects those that have not sent a message within their keep-alive interval.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Looping through all clients to check their last message time.
• How many times: Once per client each time the check runs.

How Execution Grows With Input

As the number of clients increases, the time to check all clients grows proportionally.

Input Size (n)	Approx. Operations
10	10 checks
100	100 checks
1000	1000 checks

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

Final Time Complexity

Time Complexity: O(n)

This means the time to check keep-alive status grows directly with the number of clients connected.

Common Mistake

[X] Wrong: "Checking keep-alive status is constant time no matter how many clients there are."

[OK] Correct: Each client must be checked individually, so more clients mean more checks and more time.

Interview Connect

Understanding how operations scale with input size is key to designing efficient IoT systems that handle many devices smoothly.

Self-Check

"What if the clients were grouped and only groups were checked instead of individual clients? How would the time complexity change?"