next fit probably the simplest algorithm is next fit when processing any itemwe check to see whether it fits in the same bin as the last item if it doesit is placed thereotherwisea new bin is created this algorithm is incredibly simple to implement and runs in linear time figure shows the packing produced for the same input as figure not only is next fit simple to programits worst-case behavior is also easy to analyze theorem let be the optimal number of bins required to pack list of items then next fit never uses more than bins there exist sequences such that next fit uses bins proof consider any adjacent bins bj and bj+ the sum of the sizes of all items in bj and bj+ must be larger than since otherwise all of these items would have been placed in bj if we apply this result to all pairs of adjacent binswe see that at most half of the space is wasted thus next fit uses at most twice the optimal number of bins to see that this ratio is tightsuppose that the items have size si if is odd and si / if is even assume is divisible by the optimal packingshown in figure consists of / binseach containing elements of size and one bin containing the / elements of size /nfor total of ( / figure shows that next fit uses / bins thusnext fit can be forced to use almost twice as many bins as optimal first fit although next fit has reasonable performance guaranteeit performs poorly in practicebecause it creates new bins when it does not need to in the sample runit could have placed the item of size in either or rather than create new bin the first fit strategy is to scan the bins in order and place the new item in the first bin that is large enough to hold it thusa new bin is created only when the results of previous placements have left no other alternative figure shows the packing that results from first fit on our standard input empty empty empty empty empty figure next fit for