Extensions with constraints in Swift - Time & Space Complexity

Time Complexity: Extensions with constraints

O(n²)

Understanding Time Complexity

When we add extra features to types using extensions with constraints, it's important to know how the code runs as the input grows.

We want to see how the time needed changes when the input size changes.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

extension Array where Element: Equatable {
    func containsDuplicates() -> Bool {
        for i in 0..

This code adds a function to arrays whose elements can be compared for equality. It checks if the array has any repeated items.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Two nested loops comparing pairs of elements.
• How many times: Outer loop runs once per element, inner loop runs fewer times each pass, roughly n x (n-1)/2 comparisons.

How Execution Grows With Input

As the array gets bigger, the number of comparisons grows much faster.

Input Size (n)	Approx. Operations
10	About 45 comparisons
100	About 4,950 comparisons
1000	About 499,500 comparisons

Pattern observation: The work grows roughly with the square of the input size, so doubling the input makes the work about four times bigger.

Final Time Complexity

Time Complexity: O(n²)

This means the time needed grows quickly as the array gets bigger, because it checks many pairs of elements.

Common Mistake

[X] Wrong: "Since it's just a loop inside another, it must be twice as slow when input doubles."

[OK] Correct: The time actually grows by the square, not just double, because each element is compared to many others, not just once.

Interview Connect

Understanding how nested loops affect time helps you explain your code clearly and shows you can think about efficiency, a skill useful in many coding situations.

Self-Check

"What if we changed the function to use a Set to track seen elements instead of nested loops? How would the time complexity change?"