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?"

Practice

1. What is the main purpose of using threads in Rust?

easy

A. To make the program run slower

B. To avoid using variables

C. To write code without functions

D. To run multiple parts of a program at the same time

Solution

1. Step 1: Understand what threads do

   Threads allow a program to perform multiple tasks simultaneously, improving efficiency.

2. Step 2: Match purpose with options

   Only To run multiple parts of a program at the same time correctly states that threads run parts of a program at the same time.

3. Final Answer:

   To run multiple parts of a program at the same time -> Option D

4. Quick Check:

   Threads = run tasks simultaneously [OK]

Hint: Threads let programs do many things at once [OK]

Common Mistakes:

• Thinking threads slow down the program
• Confusing threads with functions
• Believing threads remove variables

2. Which of the following is the correct way to start a new thread in Rust?

easy

A. thread::start(|| println!("Hello"));

B. thread::spawn(|| println!("Hello"));

C. thread::run(|| println!("Hello"));

D. thread::create(|| println!("Hello"));

Solution

1. Step 1: Recall Rust thread syntax

   Rust uses thread::spawn to create a new thread.

2. Step 2: Compare options with correct syntax

   Only thread::spawn(|| println!("Hello")); uses thread::spawn correctly.

3. Final Answer:

   thread::spawn(|| println!("Hello")); -> Option B

4. Quick Check:

   Start thread = thread::spawn [OK]

Hint: Use thread::spawn to start threads in Rust [OK]

Common Mistakes:

• Using thread::start instead of spawn
• Using thread::run or thread::create which don't exist
• Missing the closure syntax ||

3. What will the following Rust code print?

use std::thread;

fn main() {
    let handle = thread::spawn(|| {
        println!("Inside thread");
    });
    handle.join().unwrap();
    println!("Thread finished");
}

medium

A. Inside thread
Thread finished

B. Thread finished

C. Inside thread

D. Thread finished
Inside thread

Solution

1. Step 1: Understand thread::spawn and join

   The thread prints "Inside thread". The main thread waits for it to finish using join().

2. Step 2: Determine print order

   Because join() waits, "Inside thread" prints first, then "Thread finished" prints.

3. Final Answer:

   Inside thread Thread finished -> Option A

4. Quick Check:

   join() waits, so inside thread prints before main [OK]

Hint: join() waits for thread, so thread prints before main continues [OK]

Common Mistakes:

• Assuming main prints first without waiting
• Ignoring join() effect
• Expecting only one print line

4. Identify the error in this Rust code that uses threads:

use std::thread;

fn main() {
    let handle = thread::spawn(|| {
        println!("Hello from thread");
    });
    println!("Main thread");
}

medium

A. Missing call to join(), so main may end before thread finishes

B. thread::spawn is used incorrectly

C. println! macro is used wrong

D. No error, code runs perfectly

Solution

1. Step 1: Check thread usage

   The code starts a thread but does not wait for it to finish with join().

2. Step 2: Understand consequences

   Without join(), the main thread may finish and exit before the spawned thread prints.

3. Final Answer:

   Missing call to join(), so main may end before thread finishes -> Option A

4. Quick Check:

   Always join threads to ensure they complete [OK]

Hint: Always join threads to wait for their completion [OK]

Common Mistakes:

• Forgetting to call join()
• Thinking thread::spawn syntax is wrong
• Assuming println! is incorrect

5. You want to run two threads that each print a message, then print "Done" after both finish. Which code correctly does this?

hard

A. thread::spawn(|| println!("Thread 1")).join().unwrap();
thread::spawn(|| println!("Thread 2"));
println!("Done");

B. let t1 = thread::spawn(|| println!("Thread 1"));
let t2 = thread::spawn(|| println!("Thread 2"));
println!("Done");

C. let t1 = thread::spawn(|| println!("Thread 1"));
let t2 = thread::spawn(|| println!("Thread 2"));
t1.join().unwrap();
t2.join().unwrap();
println!("Done");

D. thread::spawn(|| println!("Thread 1"));
thread::spawn(|| println!("Thread 2"));
thread::spawn(|| println!("Done"));

Solution

1. Step 1: Understand thread creation and waiting

   To ensure "Done" prints after both threads finish, we must join both threads before printing.

2. Step 2: Analyze options for correct join usage

   let t1 = thread::spawn(|| println!("Thread 1")); let t2 = thread::spawn(|| println!("Thread 2")); t1.join().unwrap(); t2.join().unwrap(); println!("Done"); creates two threads, joins both, then prints "Done". This guarantees order.

3. Final Answer:

   let t1 = thread::spawn(|| println!("Thread 1")); let t2 = thread::spawn(|| println!("Thread 2")); t1.join().unwrap(); t2.join().unwrap(); println!("Done"); -> Option C

4. Quick Check:

   Join all threads before final print to ensure order [OK]

Hint: Join all threads before final action to ensure completion [OK]

Common Mistakes:

• Not joining threads before printing "Done"
• Joining threads immediately after spawn (serializing)
• Spawning extra thread for "Done" message