Dictionary methods and default values in Swift - Time & Space Complexity

Time Complexity: Dictionary methods and default values

O(n)

Understanding Time Complexity

When using dictionary methods with default values, it's important to know how the time to run the code changes as the dictionary grows.

We want to find out how fast dictionary lookups and updates happen when using default values.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

var counts = [String: Int]()
let words = ["apple", "banana", "apple", "orange", "banana", "apple"]

for word in words {
    counts[word, default: 0] += 1
}
    

This code counts how many times each word appears in the list using a dictionary with default values.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Looping through the words array and updating dictionary entries.
• How many times: Once for each word in the list.

How Execution Grows With Input

Each word causes one dictionary lookup and possibly an update. As the list grows, these operations happen more times.

Input Size (n)	Approx. Operations
10	About 10 lookups and updates
100	About 100 lookups and updates
1000	About 1000 lookups and updates

Pattern observation: The number of operations grows directly with the number of words.

Final Time Complexity

Time Complexity: O(n)

This means the time to count words grows in a straight line as the number of words increases.

Common Mistake

[X] Wrong: "Using default values makes dictionary lookups slower because it adds extra work."

[OK] Correct: The default value is used only when the key is missing, and dictionary lookups are still very fast, so the overall speed stays proportional to the number of words.

Interview Connect

Understanding how dictionary methods work with default values helps you write clear and efficient code, a skill valued in many programming tasks.

Self-Check

"What if we replaced the array with a nested loop over two arrays? How would the time complexity change?"