Suppose you are given a set S={j1 , j2 ,... , jn} of jobs, where job ji requires ti units of time to complete once it is started. You have one resource for running these jobs, so only one job can be run at a time. Let fi be the finish time of job ji . Your goal is to minimize the average finish time. For example, suppose there are two jobs, j1 and j2 with processing times t1=3 and t2=5. Consider the schedule in which j2 runs first followed by j1 , then f 2=5 and f 1=8 , and the average finish time is (5+8)/2 = 6.5. If we schedule the jobs in the opposite order, then f 1=3 and f 2=8 and the average finish time is (3+8)/2 = 5.5.

Give an algorithm that minimizes the average completion time and state the running time of it.