First time here? Checkout the FAQ!
+2 votes

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 (43.8k points)   | 1.8k 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

+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)

answered by Active (2.3k 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)

answered by Loyal (4.3k points)  

Related questions

+2 votes
3 answers
asked in Algorithms by bahirNaik Loyal (3.7k points)   | 125 views
+1 vote
0 answers

Top Users Sep 2017
  1. Habibkhan

    7142 Points

  2. Warrior

    2640 Points

  3. Arjun

    2480 Points

  4. rishu_darkshadow

    2466 Points

  5. A_i_$_h

    2214 Points

  6. nikunj

    1980 Points

  7. manu00x

    1846 Points

  8. makhdoom ghaya

    1770 Points

  9. Bikram

    1744 Points

  10. SiddharthMahapatra

    1718 Points

26,133 questions
33,705 answers
31,105 users