Associated types in protocols in Swift - Time & Space Complexity

Time Complexity: Associated types in protocols

O(1)

Understanding Time Complexity

We want to understand how the time it takes to run code with protocols and associated types changes as input grows.

Specifically, how does using an associated type affect the speed of operations inside a protocol?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

protocol Container {
    associatedtype Item
    var items: [Item] { get set }
    func count() -> Int
}

struct IntStack: Container {
    var items = [Int]()
    func count() -> Int {
        return items.count
    }
}
    

This code defines a protocol with an associated type and a struct that implements it with an array of items.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Accessing the array's count property inside the count() method.
• How many times: The count property is accessed once per call, which is a constant time operation.

How Execution Grows With Input

Accessing the count of an array does not depend on the number of items; it is stored internally.

Input Size (n)	Approx. Operations
10	1
100	1
1000	1

Pattern observation: The operation count stays the same no matter how many items are in the array.

Final Time Complexity

Time Complexity: O(1)

This means the time to get the count does not grow with the number of items; it stays constant.

Common Mistake

[X] Wrong: "Using an associated type makes the count operation slower because it adds complexity."

[OK] Correct: The associated type only defines the kind of items; it does not affect how fast the count property works, which is a simple stored value access.

Interview Connect

Understanding how protocols with associated types behave helps you explain how your code scales and performs, a useful skill in real projects and interviews.

Self-Check

What if the count() method instead looped through all items to count them manually? How would the time complexity change?