Bird
Raised Fist0
Operating Systemsknowledge~5 mins

SJF (Shortest Job First) in Operating Systems - Time & Space Complexity

Choose your learning style10 modes available
LearnWhyDeepVisualPracticeChallengeProjectRecallTime

Start learning this pattern below

Jump into concepts and practice - no test required

or
Recommended
Test this pattern10 questions across easy, medium, and hard to know if this pattern is strong
Time Complexity: SJF (Shortest Job First)
O(n²)
Understanding Time Complexity

Analyzing time complexity helps us understand how the scheduling process scales as more jobs arrive.

We want to know how the time to pick the next shortest job grows with the number of jobs waiting.

Scenario Under Consideration

Analyze the time complexity of the following SJF scheduling snippet.


// jobs is a list of processes with their burst times
while (jobs not empty) {
  shortest = find job with smallest burst time in jobs
  run shortest job
  remove shortest job from jobs
}

This code repeatedly selects and runs the job with the shortest burst time until all jobs are done.

Identify Repeating Operations

Look for repeated actions that take time as jobs increase.

  • Primary operation: Searching the list of jobs to find the shortest burst time.
  • How many times: Once for each job, since each job is run and removed one by one.
How Execution Grows With Input

Each time we pick a job, we scan all remaining jobs to find the shortest one.

Input Size (n)Approx. Operations
10About 10 + 9 + ... + 1 = 55 scans
100About 100 + 99 + ... + 1 = 5,050 scans
1000About 1000 + 999 + ... + 1 = 500,500 scans

Pattern observation: The total work grows roughly like the square of the number of jobs.

Final Time Complexity

Time Complexity: O(n²)

This means the time to schedule all jobs grows quickly as the number of jobs increases, roughly proportional to the square of the job count.

Common Mistake

[X] Wrong: "Finding the shortest job each time only takes constant time because we just pick one job."

[OK] Correct: Actually, without special data structures, you must check all remaining jobs each time, so the time grows with the number of jobs left.

Interview Connect

Understanding how scheduling algorithms scale helps you explain trade-offs clearly and shows you can think about efficiency beyond just correctness.

Self-Check

"What if we kept the jobs sorted by burst time from the start? How would that change the time complexity?"

Practice

(1/5)
1. What is the main goal of the SJF (Shortest Job First) scheduling algorithm?
easy
A. To schedule the shortest job next to minimize average waiting time
B. To schedule jobs in the order they arrive
C. To schedule the longest job first to maximize CPU usage
D. To schedule jobs randomly without any priority

Solution

  1. Step 1: Understand SJF scheduling principle

    SJF always picks the job with the shortest execution time next to run.

  2. Step 2: Identify the goal of SJF

    This approach reduces the average waiting time for all jobs in the queue.

  3. Final Answer:

    To schedule the shortest job next to minimize average waiting time -> Option A

  4. Quick Check:

    SJF = shortest job first, reduces waiting time [OK]
Hint: SJF picks shortest job first to reduce waiting time [OK]
Common Mistakes:
  • Confusing SJF with FCFS (First Come First Serve)
  • Thinking SJF schedules longest jobs first
  • Assuming SJF schedules jobs randomly
2. Which of the following is the correct way to describe the SJF scheduling algorithm?
easy
A. Schedules jobs based on their arrival time only
B. Schedules the job with the shortest burst time next
C. Schedules jobs in a round-robin fashion
D. Schedules jobs randomly without considering job length

Solution

  1. Step 1: Recall SJF scheduling criteria

    SJF selects the job with the shortest burst (execution) time next.

  2. Step 2: Match the description to options

    Only Schedules the job with the shortest burst time next correctly states scheduling by shortest burst time.

  3. Final Answer:

    Schedules the job with the shortest burst time next -> Option B

  4. Quick Check:

    SJF = shortest burst time scheduling [OK]
Hint: SJF = shortest burst time next, not arrival time [OK]
Common Mistakes:
  • Confusing SJF with FCFS which uses arrival time
  • Mixing SJF with round-robin scheduling
  • Ignoring job length in scheduling decision
3. Given the following jobs with their burst times:
Job A: 6 units, Job B: 2 units, Job C: 8 units, Job D: 3 units
What is the average waiting time using non-preemptive SJF scheduling?
medium
A. 5.0 units
B. 3.5 units
C. 4.5 units
D. 6.0 units

Solution

  1. Step 1: Order jobs by burst time for SJF

    Order: Job B (2), Job D (3), Job A (6), Job C (8).

  2. Step 2: Calculate waiting times for each job

    Waiting times: B=0, D=2, A=5 (2+3), C=11 (2+3+6).

  3. Step 3: Compute average waiting time

    Average = (0 + 2 + 5 + 11) / 4 = 18 / 4 = 4.5 units.

  4. Final Answer:

    4.5 units -> Option C

  5. Quick Check:

    Average waiting time = 4.5 units [OK]
Hint: Sort jobs by burst time, sum waiting times, divide by count [OK]
Common Mistakes:
  • Not sorting jobs by burst time
  • Calculating waiting time incorrectly by mixing completion times
  • Forgetting to start first job waiting time at zero
4. Consider this non-preemptive SJF schedule with jobs and burst times:
Job X: 4 units, Job Y: 3 units, Job Z: 5 units
If the scheduler mistakenly picks Job Z first, what is the main error?
medium
A. Scheduling jobs randomly
B. Scheduling jobs based on arrival time
C. Using preemptive instead of non-preemptive scheduling
D. Ignoring the shortest job first rule

Solution

  1. Step 1: Identify correct SJF behavior

    SJF should pick the job with the shortest burst time first, which is Job Y (3 units).

  2. Step 2: Analyze the mistake

    Picking Job Z (5 units) first ignores the shortest job first rule.

  3. Final Answer:

    Ignoring the shortest job first rule -> Option D

  4. Quick Check:

    Picking longer job first breaks SJF rule [OK]
Hint: SJF must pick shortest job first, not longer ones [OK]
Common Mistakes:
  • Confusing arrival time with burst time priority
  • Mixing preemptive and non-preemptive concepts
  • Assuming random scheduling is allowed in SJF
5. In a system using preemptive SJF (Shortest Remaining Time First), if a new job arrives with a burst time shorter than the remaining time of the current job, what happens?
hard
A. The new job preempts the current job immediately
B. The current job continues until completion
C. The new job waits until the current job finishes
D. Both jobs run simultaneously

Solution

  1. Step 1: Understand preemptive SJF behavior

    Preemptive SJF (Shortest Remaining Time First) allows interruption if a shorter job arrives.

  2. Step 2: Apply rule to scenario

    If new job's burst time is less than current job's remaining time, it preempts immediately.

  3. Final Answer:

    The new job preempts the current job immediately -> Option A

  4. Quick Check:

    Preemptive SJF switches to shortest remaining job [OK]
Hint: New shorter job preempts current in preemptive SJF [OK]
Common Mistakes:
  • Assuming current job always runs to completion
  • Confusing preemptive with non-preemptive SJF
  • Thinking jobs run in parallel