Protocol with associated types in Swift - Time & Space Complexity

Time Complexity: Protocol with associated types

O(n)

Understanding Time Complexity

When using protocols with associated types in Swift, it's important to understand how the code runs as input grows.

We want to see how the number of operations changes when working with these protocols.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

protocol Container {
    associatedtype Item
    mutating func append(_ item: Item)
    var count: Int { get }
    subscript(i: Int) -> Item { get }
}

struct IntStack: Container {
    var items = [Int]()
    mutating func append(_ item: Int) { items.append(item) }
    var count: Int { items.count }
    subscript(i: Int) -> Int { items[i] }
}

This code defines a protocol with an associated type and a struct that implements it for integers.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Appending items to the array inside the struct.
• How many times: Each append operation adds one item, repeated for each element added.

How Execution Grows With Input

Each time we add an item, the append operation runs once. So if we add more items, the total work grows with the number of items.

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

Pattern observation: The work grows directly with the number of items added.

Final Time Complexity

Time Complexity: O(n)

This means the time to add items grows in a straight line with the number of items.

Common Mistake

[X] Wrong: "Using a protocol with associated types makes the code slower or more complex in time."

[OK] Correct: The protocol itself doesn't add extra repeated work; the time depends on how many items you process, not on the protocol's presence.

Interview Connect

Understanding how protocols with associated types affect performance helps you write clear and efficient Swift code, a skill valuable in many coding situations.

Self-Check

"What if the append method had to search the array before adding? How would the time complexity change?"