6 The following masses, in kg, are to be packed into bins.
$$\begin{array} { l l l l l l l l l l }
8 & 5 & 9 & 7 & 7 & 9 & 1 & 3 & 3 & 8
\end{array}$$
- Chloe says that first-fit decreasing gives a packing that requires 4 bins, but first-fit only requires 3 bins. Find the maximum capacity of the bins.
First-fit requires one pass through the list and the time taken may be regarded as being proportional to the length of the list. Suppose that shuttle sort was used to sort the list into decreasing order.
- What can be deduced, in this case, about the order of the time complexity, \(\mathrm { T } ( n )\), for first-fit decreasing?