Operating Systemsknowledge~5 mins

Process creation (fork and exec) in Operating Systems - Time & Space Complexity

Choose your learning style9 modes available

Time Complexity: Process creation (fork and exec)

O(n)

Understanding Time Complexity

When a new process is created using fork and exec, it is important to understand how the time taken grows as the system handles more processes.

We want to know how the cost of creating processes changes as the number of processes increases.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.


for (int i = 0; i < n; i++) {
    pid_t pid = fork();
    if (pid == 0) {
        execve("/bin/program", args, envp);
        exit(0);
    }
}

This code creates n child processes by calling fork in a loop, then each child replaces its program image using exec.

Identify Repeating Operations

Primary operation: The loop runs fork() n times to create n processes.
How many times: The fork system call is executed once per iteration, so n times.

How Execution Grows With Input

Each new process requires a fork call, which duplicates the current process, and then an exec call to load a new program.

Pattern observation: The total work grows directly with the number of processes created.

Final Time Complexity

Time Complexity: O(n)

This means the time to create processes grows linearly with the number of processes requested.

Common Mistake

[X] Wrong: "Forking multiple processes happens all at once and takes constant time regardless of n."

[OK] Correct: Each fork call duplicates the process separately, so the total time adds up with each new process created.

Interview Connect

Understanding how process creation scales helps you reason about system performance and resource management in real applications.

Self-Check

"What if we replaced fork with a thread creation call? How would the time complexity change?"