Thread pools in Operating Systems - Time & Space Complexity

Time Complexity: Thread pools

O(n)

Understanding Time Complexity

When using thread pools, it is important to understand how the time to complete tasks changes as the number of tasks grows.

We want to know how the total work time scales when many tasks are handled by a fixed number of threads.

Scenario Under Consideration

Analyze the time complexity of the following thread pool task execution.

ThreadPool pool = new ThreadPool(4); // 4 worker threads
for (int i = 0; i < n; i++) {
    pool.submit(() -> {
        performTask(); // each task takes constant time
    });
}
pool.waitForAllTasks();
    

This code submits n tasks to a thread pool with 4 threads, each task taking the same fixed time.

Identify Repeating Operations

Look for repeated actions that affect total time.

• Primary operation: Executing each of the n tasks.
• How many times: Each task runs once, total n tasks.
• The thread pool runs up to 4 tasks at the same time, but all n tasks must complete.

How Execution Grows With Input

As the number of tasks n increases, total work grows linearly because each task takes constant time.

Input Size (n)	Approx. Operations (task executions)
10	10 tasks executed
100	100 tasks executed
1000	1000 tasks executed

Pattern observation: Doubling the number of tasks roughly doubles the total work time, even with parallel threads.

Final Time Complexity

Time Complexity: O(n)

This means the total time grows directly in proportion to the number of tasks, despite running some in parallel.

Common Mistake

[X] Wrong: "Using a thread pool with multiple threads makes the total time constant regardless of tasks."

[OK] Correct: Even with multiple threads, all tasks must run, so total time still grows with the number of tasks, just faster than one thread.

Interview Connect

Understanding how thread pools affect time helps you explain real-world program performance and shows you can reason about parallel work efficiently.

Self-Check

What if the thread pool size increased with the number of tasks? How would the time complexity change?