The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+3 votes
2.2k 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)

Made Easy

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

Q 19

Please give reference for this answer to this algorithm.

asked in Algorithms by Veteran (46.8k points) | 2.2k views

@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.

2 Answers

+2 votes

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)

answered by Active (2.4k points)
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/

answered by Loyal (4.5k points)

Related questions

+2 votes
3 answers
1
asked in Algorithms by bahirNaik Loyal (3.7k points) | 133 views
+2 votes
1 answer
3


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

28,947 questions
36,793 answers
91,077 comments
34,690 users