Threads overview in Rust - Time & Space Complexity

Time Complexity: Threads overview

O(n)

Understanding Time Complexity

When using threads, we want to know how the program's work grows as we add more tasks or data.

We ask: How does running multiple threads affect the total steps the program takes?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

use std::thread;

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

This code creates 5 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 running 5 threads.
• How many times: 5 times, once per thread.

How Execution Grows With Input

As the number of threads increases, the total work grows roughly the same amount.

Input Size (n)	Approx. Operations
5	5 thread creations and joins
10	10 thread creations and joins
100	100 thread creations and joins

Pattern observation: Doubling threads roughly doubles the work done.

Final Time Complexity

Time Complexity: O(n)

This means the total steps grow directly with the number of threads created.

Common Mistake

[X] Wrong: "Adding more threads makes the program run faster without extra cost."

[OK] Correct: Creating and managing threads takes time, so more threads mean more work overall.

Interview Connect

Understanding how threads add work helps you explain program speed and resource use clearly.

Self-Check

"What if we changed the number of threads to grow with input size? How would the time complexity change?"