Question

Give a polynomial-time algorithm that takes a sequence of supply values s1, s2, . . . , sn and returns a schedule of minimum cost. for example, suppose r = 1, c = 10, and the sequence of values is

Answer 1

Assuming the sequence is unsorted.

Try a rudimentary proposition, do a bubble sort, that gives O(n^2) for worst and average case. It is a polynomial algorithm.

We can also do a quick sort, with worst case O(n^2) and average case O(nlogn), which is already better.

Do we need to sort everything? Not really.

What about a single pass, and store the minimum found, exchange as required, such as:

small=A(0)
for i:1, n {
if A(i)<small small: A(i)
}
return small

This is a linear algorithm, best case n, worst case 2n so O(n)