Wildcard subscriptions (+ and #) in IOT Protocols - Time & Space Complexity

Time Complexity: Wildcard subscriptions (+ and #)

O(n)

Understanding Time Complexity

When using wildcard subscriptions in IoT protocols, it's important to know how the system handles matching topics. We want to understand how the work grows as more topics or subscriptions are involved.

The question is: how does the matching process scale when wildcards like + and # are used?

Scenario Under Consideration

Analyze the time complexity of the following subscription matching logic.

function matchTopic(subscription, topic) {
  let subLevels = subscription.split('/');
  let topicLevels = topic.split('/');

  for (let i = 0; i < subLevels.length; i++) {
    if (subLevels[i] === '#') return true;
    if (subLevels[i] !== '+' && subLevels[i] !== topicLevels[i]) return false;
  }
  return subLevels.length === topicLevels.length;
}

This code checks if a topic matches a subscription that may include + or # wildcards.

Identify Repeating Operations

Look for loops or repeated checks.

• Primary operation: Loop through each level of the subscription topic.
• How many times: Up to the number of levels in the subscription (n).

How Execution Grows With Input

The time to check a match grows as the number of topic levels increases.

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

Pattern observation: The work grows linearly with the number of topic levels.

Final Time Complexity

Time Complexity: O(n)

This means the matching time increases in direct proportion to the number of topic levels.

Common Mistake

[X] Wrong: "Wildcard matching happens instantly regardless of topic length."

[OK] Correct: Each topic level must be checked one by one, so longer topics take more time to match.

Interview Connect

Understanding how wildcard matching scales helps you design efficient IoT systems and shows you can think about performance in real-world messaging scenarios.

Self-Check

What if the subscription used multiple # wildcards in different positions? How would that affect the time complexity?