# Question & Answer: Choose one of the theorems about optimality of scheduling algorithms and prove it.it is necessa…..

Choose one of the theorems about optimality of scheduling algorithms and prove it.it is necessary to write a formal proof, but you should at least sketch informally all the main ideas. You may also formulate your own algorithm ( for one of the studied problems) and prove its optimality

We will prove that the schedule S provided by the Greedy algorithm shown in class schedules n events at least as quickly as any other competing schedule S’.

Base case: n=1. Because S schedules the event that finishes first out of all possible events, S must finish scheduling 1 event before or exactly when S’ does.

Inductive hypothesis: Assume for an arbitrary value of n=k that S schedules k events at least as quickly as any competing schedule S’. (We can say that S has an ending time of t while any competing schedule S’ has an ending time of t’, and that the hypothesis is that t £ t’.)

Inductive step: Prove for n=k+1 that S schedules k+1 events at least as quickly as any competing schedule S’.

In order to prove the inductive step, we start with the inductive hypothesis. We know that that t £ t’. Thus, S is allowed to schedule any event with a start time greater than or equal to t, while S’ is allowed to schedule any event with a start time greater than or equal to t’. Thus, S is allowed to schedule any event S’ is allowed to schedule. Of those allowable events, if S chooses one, it will be the one that finishes first. It would be impossible for S’ to pick one from the set that finishes before the one that finishes first in the set. Thus, we have shown for n=k+1, that S schedules k+1 events at least as quickly as S’ does.