Equatable, Hashable, Comparable protocols in Swift - Time & Space Complexity

Time Complexity: Equatable, Hashable, Comparable protocols

O(n)

Understanding Time Complexity

When using Equatable, Hashable, and Comparable protocols, we want to know how fast these operations run as data grows.

We ask: How does the time to compare or hash items change with more data?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

struct Person: Equatable, Hashable, Comparable {
    let id: Int
    let name: String

    static func == (lhs: Person, rhs: Person) -> Bool {
        return lhs.id == rhs.id
    }

    func hash(into hasher: inout Hasher) {
        hasher.combine(id)
    }

    static func < (lhs: Person, rhs: Person) -> Bool {
        return lhs.id < rhs.id
    }
}
    

This code defines how to check equality, create a hash, and compare two Person objects.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Comparing or hashing the id property.
• How many times: Each comparison or hash runs once per call, but when used in collections, these operations repeat for many items.

How Execution Grows With Input

Each comparison or hash runs in constant time, but when checking many items, total time grows with the number of items.

Input Size (n)	Approx. Operations
10	10 comparisons or hashes
100	100 comparisons or hashes
1000	1000 comparisons or hashes

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

Final Time Complexity

Time Complexity: O(n)

This means the time to compare or hash many items grows in a straight line as you add more items.

Common Mistake

[X] Wrong: "Comparing two objects always takes longer as the list grows."

[OK] Correct: Comparing two objects depends only on their properties, not the list size. The list size affects how many times you do comparisons, not the cost of one comparison.

Interview Connect

Understanding how these protocols work helps you explain how your code handles data efficiently, a skill useful in many coding challenges and real projects.

Self-Check

"What if the name property was a long string instead of a short one? How would that affect the time complexity of comparison?"