Message passing concepts in Rust - Time & Space Complexity

Time Complexity: Message passing concepts

O(n)

Understanding Time Complexity

When using message passing in Rust, it's important to know how the time to send and receive messages changes as the number of messages grows.

We want to understand how the program's speed changes when more messages are passed between threads.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

use std::sync::mpsc;
use std::thread;

let n = 10; // example value for n
let (tx, rx) = mpsc::channel();

thread::spawn(move || {
    for i in 0..n {
        tx.send(i).unwrap();
    }
});

for _ in 0..n {
    let _ = rx.recv().unwrap();
}
    

This code sends n messages from one thread to another using a channel, then receives them all.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Sending and receiving messages inside loops.
• How many times: Each loop runs n times, sending and receiving one message per iteration.

How Execution Grows With Input

As the number of messages n increases, the total send and receive operations grow directly with n.

Input Size (n)	Approx. Operations
10	About 20 (10 sends + 10 receives)
100	About 200 (100 sends + 100 receives)
1000	About 2000 (1000 sends + 1000 receives)

Pattern observation: The total operations increase in a straight line as n grows.

Final Time Complexity

Time Complexity: O(n)

This means the time to send and receive messages grows directly with the number of messages.

Common Mistake

[X] Wrong: "Sending messages happens instantly, so time does not grow with more messages."

[OK] Correct: Each message requires work to send and receive, so more messages mean more total time.

Interview Connect

Understanding how message passing scales helps you write programs that handle many tasks smoothly and shows you can think about program speed clearly.

Self-Check

"What if we used multiple sender threads instead of one? How would the time complexity change?"