Question

What is the time complexity of job sequencing with deadline using greedy algorithm?

• O(n)
• O(log n)
• O(n log n)
• O(n2)

Made Easy

Full Syllabus Test-6 : Basic Level : Practice Test-14

Q 19

Please give reference for this answer to this algorithm.

Comments

http://ocw.mit.edu/courses/civil-and-environmental-engineering/1-204-computer-algorithms-in-systems-engineering-spring-2010/lecture-notes/MIT1_204S10_lec10.pdf

---

@Anurag Pandey ,

It seems like you have virtually answered the question :) It should be O(N) as per this lecture notes. Let me read it through. Thanks for reference. (You should add answer , if you are sure it is correct, & I think it will be mostly as it is MIT !)

---

Though do we need to sort ? Before O(N) algorithm stated there ? In that case, wont this come down to O(NlogN). I'm yet reading it , so now I've not realized, whether it does sorting even in Fast algorithm !

---

I read it superficially, I guess we need sorting to resolve sequencing conflicts among the jobs that have same deadlines.

Answer 1

1. sort job according to decresing order of deadline =  O(nlogn)

2.for each job find slot in array of size n = O(n^2)

total time  = O(nlogn) + O(n^2) =O(n^2)

Comments

Can you give me reference to this algorithm ? (Actually I know the formal procedure, just want to be sure N^2 is correct lower bound !

Also the always asked question in case algorithm, can we do better ? (In case of greedy or using other methods ? :) )

---

It is given that we can optimize job sequencing using disjoint data structure. Can you please explai nhow it is possible?

---

It is not array of size n. size of array will be max deadline(d).
So. more precisely,
final Time complexity should be, O(nlogn)(for sorting) + O(d*n) = O(d*n)

Now, if we assume d = n then time complexity = O(n^2)

Answer 2

1) To sort N Job - O(nlogn).

2)  Take each job and start where the deadline is given ans keep searching for the vaccant location. So if there are N jobs for each job we need to search N slots. i.e O(n^2)

so total time complexity is O(n^2)

http://www.geeksforgeeks.org/job-sequencing-problem-set-1-greedy-algorithm/

Answer 3

Step 1.

Look for the highest deadline - O(n)

Step 2.

Make an subset array to hold the completed jobs of size equal to max deadline & initialize it to 0. - O(n)

Step 3.

Sort the jobs in decreasing order of profit - theta(nlogn)

Step 4.

Place the job in required deadline. If a deadline is occupied, look for all previous deadlines untill an empty slot is found.- O(n^2)

Total time complexity O(n^2) [AC & WC]

For best case, when every job has diff. deadline TC will be theta(nlogn).