1.8k views

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

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

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

Q 19

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.

+1 vote

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)

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 ? :) )
+1 vote

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/