0

What is the space complexity of maintaining k stacked decorators wrapping a core object in the Decorator Pattern?

medium🪤 Complexity Trap Q6 of Q15

OOP & Design Patterns - Decorator Pattern - Wrapping Behaviour Without Subclassing

What is the space complexity of maintaining k stacked decorators wrapping a core object in the Decorator Pattern?

AO(log k) -- logarithmic due to tree structure

BO(k) -- linear in number of decorators

CO(k²) -- quadratic due to nested references

DO(1) -- only one object stored

Step-by-Step Solution

Solution:

Step 1: Analyze decorator storage
Each decorator stores a reference to the wrapped object, forming a chain of length k.
Step 2: Consider call stack during method calls
Method calls traverse the chain, creating a call stack of depth k -> O(k) auxiliary space.
Step 3: Recognize that actual stored objects are k, but call stack is also O(k)
Overall space complexity is O(k) for objects and call stack.
Final Answer:
Option B -> Option B
Quick Check:
Each decorator object stored plus call stack frame -> linear space [OK]

Quick Trick: Each decorator adds one object and call stack frame -> O(k) space [OK]

Common Mistakes:

MISTAKES

Forgetting call stack space
Assuming constant space despite chain
Confusing nested references with quadratic space

Trap Explanation:

PITFALL

Candidates often underestimate space due to ignoring recursion stack or chain references.

Interviewer Note:

CONTEXT

Tests understanding of memory usage in decorator chains including call stack.

Master "Decorator Pattern - Wrapping Behaviour Without Subclassing" in OOP & Design Patterns

2 interactive learning modes - each teaches the same concept differently

Want More Practice?

15+ quiz questions · All difficulty levels · Free

Free Signup - Practice All Questions

More OOP & Design Patterns Quizzes