SNS topics and subscriptions in AWS - Time & Space Complexity

Time Complexity: SNS topics and subscriptions

O(n)

Understanding Time Complexity

When working with SNS topics and subscriptions, it's important to understand how the number of subscriptions affects the time it takes to manage or send messages.

We want to know how the work grows as we add more subscriptions to a topic.

Scenario Under Consideration

Analyze the time complexity of the following operation sequence.

# Create an SNS topic
aws sns create-topic --name MyTopic

# Subscribe multiple endpoints to the topic
for endpoint in endpoints_list:
  aws sns subscribe --topic-arn MyTopicArn --protocol email --notification-endpoint endpoint

# Publish a message to the topic
aws sns publish --topic-arn MyTopicArn --message "Hello Subscribers"
    

This sequence creates a topic, adds many subscriptions, and sends a message to all subscribers.

Identify Repeating Operations

• Primary operation: Subscribing endpoints to the topic using sns subscribe.
• How many times: Once for each endpoint in the subscription list.
• Message delivery: When publishing, SNS sends the message to all subscribed endpoints.
• Dominant operation: The subscription calls and message delivery scale with the number of subscribers.

How Execution Grows With Input

As the number of subscriptions grows, the number of API calls to subscribe grows directly with it. Also, when publishing, the message is sent to each subscriber individually.

Input Size (n)	Approx. Api Calls/Operations
10	10 subscribe calls + 10 message deliveries
100	100 subscribe calls + 100 message deliveries
1000	1000 subscribe calls + 1000 message deliveries

Pattern observation: The work grows linearly as the number of subscriptions increases.

Final Time Complexity

Time Complexity: O(n)

This means the time or work needed grows directly in proportion to the number of subscriptions.

Common Mistake

[X] Wrong: "Adding more subscriptions won't affect message delivery time much because SNS handles it internally."

[OK] Correct: Each subscription means SNS must send a message to one more endpoint, so delivery time grows with the number of subscribers.

Interview Connect

Understanding how SNS scales with subscriptions helps you design systems that handle many users efficiently and shows you can think about how cloud services behave as they grow.

Self-Check

"What if we batch messages to multiple subscribers at once? How would the time complexity change?"