Extending built-in types in Swift - Time & Space Complexity

Time Complexity: Extending built-in types

O(n)

Understanding Time Complexity

When we add new features to built-in types in Swift, it's important to know how this affects the time it takes to run our code.

We want to find out how the time to run grows as the input size changes when using these extensions.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

extension Array where Element == Int {
    func doubledElements() -> [Int] {
        var result = [Int]()
        for item in self {
            result.append(item * 2)
        }
        return result
    }
}

let numbers = [1, 2, 3, 4, 5]
let doubled = numbers.doubledElements()
    

This code adds a new function to arrays of integers that creates a new array with each number doubled.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The for-loop that goes through each item in the array.
• How many times: It runs once for every element in the array.

How Execution Grows With Input

As the array gets bigger, the function takes longer because it doubles each item one by one.

Input Size (n)	Approx. Operations
10	10 times doubling
100	100 times doubling
1000	1000 times doubling

Pattern observation: The time grows directly with the number of items; double the items means double the work.

Final Time Complexity

Time Complexity: O(n)

This means the time to run grows in a straight line with the number of elements in the array.

Common Mistake

[X] Wrong: "Adding a function to a built-in type makes the code run instantly or slower regardless of input size."

[OK] Correct: The time depends on what the function does. If it processes each item, time grows with input size, not just because it is an extension.

Interview Connect

Understanding how extending built-in types affects time helps you write clear and efficient code, a skill valued in many coding challenges and real projects.

Self-Check

"What if the extension function used recursion instead of a loop? How would the time complexity change?"