edited by
23,387 views
6 votes
6 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.

edited by

3 Answers

11 votes
11 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)

0 votes
0 votes
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).
Answer:

Related questions

4 votes
4 votes
3 answers
1
Lakshman Bhaiya asked Nov 10, 2018
12,278 views
If job $J=(J_{1},J_{2},J_{3},J_{4})$ are given their processing time $T_{i}=(1,1,2,3)$ and deadline are $D_{i}=(3,4,2,3)$ maximum how many job can be done$?$$A)1$ ...
3 votes
3 votes
3 answers
2
firki lama asked Jan 12, 2017
13,313 views
i know time complexity is O(nlogn) but can upper bound given in question consider as TRUE..