Merge and update methods in Ruby - Time & Space Complexity

Time Complexity: Merge and update methods

O(m + n)

Understanding Time Complexity

When we use merge or update methods in Ruby hashes, we want to know how the time it takes changes as the hashes get bigger.

We ask: How does the work grow when we combine or change hashes? Let m be the size of the first hash, n the size of the second.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

hash1 = { a: 1, b: 2, c: 3 }
hash2 = { b: 4, d: 5 }

result = hash1.merge(hash2) do |key, old_val, new_val|
  old_val + new_val
end

# result is { a: 1, b: 6, c: 3, d: 5 }

This code merges two hashes, combining values for keys that appear in both.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operations: 1. Duplicating all key-value pairs from the first hash (O(m)). 2. Iterating over each key-value pair in the second hash, with lookups and updates (O(n) total).
• How many times: Duplication once per element in first (m times), iteration once per element in second (n times).

How Execution Grows With Input

As either hash gets bigger, the method does more work proportionally.

Sizes (m, n)	Approx. Operations
(10, 10)	About 20
(100, 100)	About 200
(1000, 1000)	About 2000

Pattern observation: The work grows linearly with the combined size of both hashes.

Final Time Complexity

Time Complexity: O(m + n)

This means the time to merge grows linearly with the sizes of both hashes.

Common Mistake

[X] Wrong: "Merging two hashes takes time based only on the second hash."

[OK] Correct: Ruby's merge method first duplicates the first hash (O(m)), then loops over the second (O(n)). Time depends on both.

Interview Connect

Understanding how merge and update methods scale helps you write efficient code when combining data, a common task in many programs. Note merge! is O(n) as it modifies in place without duplication.

Self-Check

"What if we used merge! instead of merge? How would the time complexity change?"

Answer: It becomes O(n), since no duplication of the first hash; only iterates over the second.