Observer pattern in PHP - Time & Space Complexity

Time Complexity: Observer pattern

O(n)

Understanding Time Complexity

When using the Observer pattern, we want to know how the time to notify observers changes as we add more observers.

We ask: How does notifying all observers grow with the number of observers?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

class Subject {
    private array $observers = [];

    public function attach(callable $observer): void {
        $this->observers[] = $observer;
    }

    public function notify(): void {
        foreach ($this->observers as $observer) {
            $observer();
        }
    }
}
    

This code stores a list of observers and calls each one when notifying.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Looping through all observers to call them.
• How many times: Once for each observer in the list.

How Execution Grows With Input

As the number of observers grows, the time to notify grows too, because each observer is called once.

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

Pattern observation: The number of calls grows directly with the number of observers.

Final Time Complexity

Time Complexity: O(n)

This means the time to notify all observers grows linearly as we add more observers.

Common Mistake

[X] Wrong: "Notifying observers is always fast and constant time no matter how many observers there are."

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

Interview Connect

Understanding how notifying observers scales helps you design systems that stay responsive as they grow.

Self-Check

"What if each observer itself notifies other observers? How would that affect the time complexity?"