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?

Practice

1. What does the MQTT wildcard + represent in topic subscriptions?

easy

A. It matches zero or more topic levels.

B. It matches exactly one topic level.

C. It matches the entire topic string.

D. It matches only the last topic level.

Solution

1. Step 1: Understand the + wildcard meaning

   The + wildcard matches exactly one topic level in MQTT subscriptions.

2. Step 2: Compare with other wildcards

   The # wildcard matches zero or more levels, so it is different from +.

3. Final Answer:

   It matches exactly one topic level. -> Option B

4. Quick Check:

   + = one level [OK]

Hint: Remember: + means one level only [OK]

Common Mistakes:

• Confusing + with # wildcard
• Thinking + matches multiple levels
• Assuming + matches zero levels

2. Which of the following is the correct MQTT subscription syntax to match all topics under home/kitchen including sub-levels?

easy

A. home/kitchen/#

B. home/+/kitchen

C. home/kitchen/+

D. home/#/kitchen

Solution

1. Step 1: Identify the wildcard for all sub-levels

   The # wildcard matches all remaining topic levels, including zero or more sub-levels.

2. Step 2: Apply to the topic home/kitchen

   Using home/kitchen/# subscribes to home/kitchen and any deeper topics like home/kitchen/temperature.

3. Final Answer:

   home/kitchen/# -> Option A

4. Quick Check:

   # matches all sub-levels [OK]

Hint: Use # to catch all subtopics under a path [OK]

Common Mistakes:

• Using + instead of # for multiple levels
• Placing # in the middle of the topic
• Using invalid syntax like # in the middle

3. Given the subscription building/+/temperature, which of these topics will be matched?

medium

A. building/floor1/temperature

B. building/floor1/room1/temperature

C. building/temperature

D. building/floor1/humidity

Solution

1. Step 1: Understand the + wildcard position

   The + wildcard matches exactly one topic level between building and temperature.

2. Step 2: Check each topic against the pattern

   Topic building/floor1/temperature matches because floor1 fills the + wildcard. Others either have too many or too few levels or wrong last level.

3. Final Answer:

   building/floor1/temperature -> Option A

4. Quick Check:

   + matches one level only [OK]

Hint: + matches exactly one level between slashes [OK]

Common Mistakes:

• Matching topics with extra levels
• Ignoring the exact position of +
• Assuming + matches zero levels

4. You wrote the subscription sensor/#/temperature but it does not work. What is the problem?

medium

A. The subscription is missing a leading slash.

B. The + wildcard should be used instead of # here.

C. The topic levels are case sensitive and must be lowercase.

D. The # wildcard must be at the end of the topic filter.

Solution

1. Step 1: Recall the rule for # wildcard placement

   The # wildcard must be the last character in the topic filter and can only appear once.

2. Step 2: Analyze the subscription sensor/#/temperature

   Here, # is in the middle, which is invalid syntax and causes the subscription to fail.

3. Final Answer:

   The # wildcard must be at the end of the topic filter. -> Option D

4. Quick Check:

   # only at end [OK]

Hint: # must be last in topic filter [OK]

Common Mistakes:

• Placing # in the middle of topic
• Confusing + and # usage
• Ignoring MQTT topic syntax rules

5. You want to subscribe to all topics under office but only one level deep, such as office/room1 and office/room2, but not office/room1/temperature. Which subscription should you use?

hard

A. office/+/+

B. office/#

C. office/+

D. office

Solution

1. Step 1: Understand the requirement for one level deep

   You want to match topics exactly one level below office, like office/room1.

2. Step 2: Choose the correct wildcard

   The + wildcard matches exactly one level, so office/+ matches office/room1 but not office/room1/temperature.

3. Final Answer:

   office/+ -> Option C

4. Quick Check:

   One level deep = use + wildcard [OK]

Hint: Use + for exactly one sub-level [OK]

Common Mistakes:

• Using # which matches all levels
• Using multiple + wildcards incorrectly
• Not including any wildcard