What is the time complexity of job sequencing with deadline using greedy algorithm?
Full Syllabus Test-6 : Basic Level : Practice Test-14
Please give reference for this answer to this algorithm.
@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 !)
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)
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)