Topics and subscriptions in GCP - Time & Space Complexity

Time Complexity: Topics and subscriptions

O(n + m)

Understanding Time Complexity

When working with topics and subscriptions in cloud messaging, it is important to understand how the time to process messages grows as the number of messages or subscriptions increases.

We want to know how the number of operations changes when we add more messages or subscribers.

Scenario Under Consideration

Analyze the time complexity of the following operation sequence.

// Create a topic
const topic = pubsub.topic('my-topic');

// Create multiple subscriptions
for (let i = 0; i < n; i++) {
  topic.createSubscription(`sub-${i}`);
}

// Publish m messages to the topic
for (let j = 0; j < m; j++) {
  topic.publishMessage({ data: Buffer.from(`message ${j}`) });
}

This sequence creates n subscriptions to a topic and publishes m messages to it.

Identify Repeating Operations

Identify the API calls, resource provisioning, data transfers that repeat.

• Primary operation: Creating subscriptions and publishing messages.
• How many times: Creating subscriptions happens n times; publishing messages happens m times.

How Execution Grows With Input

As the number of subscriptions (n) increases, the number of subscription creation calls grows linearly. Similarly, publishing m messages grows linearly with m.

Input Size (n subscriptions, m messages)	Approx. API Calls/Operations
10, 10	About 20 calls (10 createSubscription + 10 publish)
100, 100	About 200 calls
1000, 1000	About 2000 calls

Pattern observation: The total operations grow roughly in direct proportion to the sum of subscriptions and messages.

Final Time Complexity

Time Complexity: O(n + m)

This means the time to complete these operations grows linearly with the number of subscriptions plus the number of messages.

Common Mistake

[X] Wrong: "Publishing messages to a topic with many subscriptions takes longer for each message because it sends to all subscribers at once."

[OK] Correct: Publishing a message is a single operation; the message fan-out to subscriptions happens asynchronously and does not increase the publish call time.

Interview Connect

Understanding how operations scale with the number of subscriptions and messages helps you design efficient messaging systems and answer questions about system behavior under load.

Self-Check

"What if we batch publish messages instead of publishing one by one? How would the time complexity change?"