Question

Exercises $37and38$deal with the problem of scheduling the most talks possible given the start and end times of n talks.

Find the complexity of the greedy algorithm for scheduling the most talks by adding at each step the talk with the earliest end time compatible with those already scheduled (Algorithm $7$in Section $3.1$). Assume that the talks are not already sorted by earliest end time and assume that the worst-case time complexity of sorting is $O(n\log n)$.

Short answer

$O\left(n^2\right)$

Step-by-step solution

Step 1

Given: is the time complexity of sorting.

Greedy algorithm for scheduling talks.

Procedure- schedule $(s_1,s_2,...,s_n:starttimesoftalks,e_1>e_2>...>e_n;n:endingtimesoftalks)$

Sort talks by finish time and reorder so that $e_1\le e_2\le ...\le e_n$.

role="math" localid="1668661065601" $S:=\varphi$

for$j:=1ton$

if talk j is compatible with S then

$S:=S\cup talkj$

return S.

Step 2

SOLUTION

The algorithm makes 1 comparison in each iteration of the for-loop (talk j is compatible with S).

Since j can take on the values from 1 to n, j can take on n values and thus there are most n iterations of the for-loop.

However to determine if talk j is compatible with S, we need to check if every element of S is compatible with talk j which will require at most n - 1 iterations (since S can contain at most n - 1 elements since the nth element will be added after the checks of compatibility).

The number of comparisons is then the product of the number of comparisons per iteration and the number of iterations (Note: product since the loops are nested).

Number of comparisons $=1\cdot n\cdot (n-1)=n(n-1)=n^2-n$

Now including the complexity of sorting, the time complexity of the algorithm becomes: $O(max(n^2,nlogn)=O(n^2)$.