Publisher-subscriber execution model in C Sharp (C#) - Time & Space Complexity

Time Complexity: Publisher-subscriber execution model

O(n)

Understanding Time Complexity

When using the publisher-subscriber model, we want to know how the time to notify subscribers grows as more subscribers join.

We ask: How does notifying all subscribers take longer when there are more subscribers?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

public class Publisher
{
    private List<Action> subscribers = new List<Action>();

    public void Subscribe(Action subscriber) {
        subscribers.Add(subscriber);
    }

    public void Notify() {
        foreach (var subscriber in subscribers) {
            subscriber();
        }
    }
}

This code lets subscribers register, then the publisher calls all subscriber actions when notifying.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The foreach loop that calls each subscriber.
• How many times: Once for each subscriber in the list.

How Execution Grows With Input

As the number of subscribers grows, the time to notify grows in a straight line.

Input Size (n)	Approx. Operations
10	10 calls to subscriber actions
100	100 calls to subscriber actions
1000	1000 calls to subscriber actions

Pattern observation: Doubling subscribers doubles the work to notify them all.

Final Time Complexity

Time Complexity: O(n)

This means notifying subscribers takes time proportional to how many subscribers there are.

Common Mistake

[X] Wrong: "Notifying subscribers is always fast and constant time no matter how many subscribers exist."

[OK] Correct: Each subscriber must be called, so more subscribers mean more calls and more time.

Interview Connect

Understanding how event notification scales helps you design systems that stay responsive as they grow.

Self-Check

What if notifying subscribers was done asynchronously in parallel? How would the time complexity change?