Default values for missing keys in Ruby - Time & Space Complexity

Time Complexity: Default values for missing keys

O(n)

Understanding Time Complexity

When we use default values for missing keys in a hash, we want to know how this choice affects how long the program takes to run.

We ask: How does the time to find or set a default value change as the hash grows?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

hash = Hash.new(0)
keys = ["a", "b", "c", "d", "e"]

keys.each do |key|
  hash[key] += 1
end

value = hash["z"]
    

This code creates a hash with a default value of 0, counts keys, and accesses a missing key.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Looping over the keys array and accessing/updating the hash.
• How many times: Once for each key in the array (5 times here).

How Execution Grows With Input

Each key is processed once, and each hash access is quick regardless of size.

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

Pattern observation: The time grows directly with the number of keys processed.

Final Time Complexity

Time Complexity: O(n)

This means the time to process keys grows in a straight line with the number of keys.

Common Mistake

[X] Wrong: "Setting a default value makes hash lookups slower as the hash grows."

[OK] Correct: Hash lookups stay fast because Ruby hashes use efficient methods internally, so default values do not slow down access noticeably.

Interview Connect

Understanding how default values affect hash access time helps you explain how data structures work efficiently in real programs.

Self-Check

"What if we changed the default value from a fixed number to a block that computes a value? How would the time complexity change?"