Creating threads in Rust - Performance & Efficiency

Time Complexity: Creating threads

O(n)

Understanding Time Complexity

When we create threads in Rust, we want to know how the time to start them changes as we create more threads.

We ask: How does the work grow when we add more threads?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

use std::thread;

fn main() {
    let n = 100usize;
    let mut handles = vec![];
    for i in 0..n {
        let handle = thread::spawn(move || {
            println!("Thread {} is running", i);
        });
        handles.push(handle);
    }
    for handle in handles {
        handle.join().unwrap();
    }
}

This code creates n threads, each printing a message, then waits for all to finish.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Loop creating and starting threads n times.
• How many times: Exactly once per thread, so n times.

How Execution Grows With Input

Each new thread adds a fixed amount of work to start and run.

Input Size (n)	Approx. Operations
10	About 10 thread starts and joins
100	About 100 thread starts and joins
1000	About 1000 thread starts and joins

Pattern observation: The work grows directly with the number of threads.

Final Time Complexity

Time Complexity: O(n)

This means the time to create and wait for threads grows in a straight line as we add more threads.

Common Mistake

[X] Wrong: "Creating threads is instant and does not add time as we add more."

[OK] Correct: Each thread takes some time to start and finish, so more threads mean more total time.

Interview Connect

Understanding how thread creation time grows helps you write programs that use threads wisely and explain your choices clearly.

Self-Check

"What if we reused a fixed number of threads instead of creating new ones each time? How would the time complexity change?"