simple method of implementing first fit would process each item by scanning down the list of bins sequentially this would take ( it is possible to implement first fit to run in ( log )we leave this as an exercise moment' thought will convince you that at any pointat most one bin can be more than half emptysince if second bin were also half emptyits contents would fit into the first bin thuswe can immediately conclude that first fit guarantees solution with at most twice the optimal number of bins on the other handthe bad case that we used in the proof of next fit' performance bound does not apply for first fit thusone might wonder if better bound can be proven the answer is yesbut the proof is complicated theorem let be the optimal number of bins required to pack list of items then first fit never uses more than bins there exist sequences such that first fit uses ( bins proof see the references at the end of the an example where first fit does almost as poorly as the previous theorem would indicate is shown in figure the input consists of items of size followed by items of size followed by items of size one simple packing places one item of each size in bin and requires bins first fit requires bins when first fit is run on large number of items with sizes uniformly distributed between and empirical results show that first fit uses roughly percent more bins than optimal in many casesthis is quite acceptable best fit the third online strategy we will examine is best fit instead of placing new item in the first spot that is foundit is placed in the tightest spot among all bins typical packing is shown in figure empty empty empty -bm bm+ - + - figure case where first fit uses bins instead of