Thread synchronization with Mutex in Ruby - Time & Space Complexity

Time Complexity: Thread synchronization with Mutex

O(n)

Understanding Time Complexity

When using threads with a mutex, we want to see how the program's speed changes as more work is done.

We ask: How does locking and unlocking affect the time as the input grows?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

require 'thread'

mutex = Mutex.new
counter = 0

threads = 10.times.map do
  Thread.new do
    1000.times do
      mutex.synchronize do
        counter += 1
      end
    end
  end
end

threads.each(&:join)

This code creates 10 threads, each adding 1 to a shared counter 1000 times, using a mutex to avoid conflicts.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The inner loop runs 1000 times per thread, each time locking and unlocking the mutex to update the counter.
• How many times: 10 threads x 1000 times = 10,000 total synchronized increments.

How Execution Grows With Input

As the number of threads or increments grows, the total locking operations grow proportionally.

Input Size (n)	Approx. Operations
10 threads x 1000 increments	10,000 mutex locks/unlocks
10 threads x 10,000 increments	100,000 mutex locks/unlocks
100 threads x 10,000 increments	1,000,000 mutex locks/unlocks

Pattern observation: The total operations grow directly with the number of threads and increments combined.

Final Time Complexity

Time Complexity: O(n)

This means the time grows in a straight line with the total number of increments across all threads.

Common Mistake

[X] Wrong: "Using a mutex makes the program run in constant time regardless of input size."

[OK] Correct: Each lock and unlock still takes time, so as the number of increments grows, the total time grows too.

Interview Connect

Understanding how mutex locking affects time helps you write safe and efficient multi-threaded programs, a useful skill in many real projects.

Self-Check

"What if we replaced the mutex with a lock-free atomic operation? How would the time complexity change?"