optimal first fit decreasing / / empty empty / / / / / / / / / / / / / / / / / / - empty / figure example where first fit decreasing uses binsbut only bins are required theorem let be the optimal number of bins required to pack list of items then first fit decreasing never uses more than bins there exist sequences such that first fit decreasing uses bins proof the upper bound requires very complicated analysis the lower bound is exhibited by sequence consisting of elements of size followed by elements of size followed by elements of size followed by elements of size figure shows that the optimal packing requires binsbut first fit decreasing uses bins set and the result follows in practicefirst fit decreasing performs extremely well if sizes are chosen uniformly over the unit intervalthen the expected number of extra bins is mbin packing is fine example of how simple greedy heuristics can give good results divide and conquer another common technique used to design algorithms is divide and conquer divide-andconquer algorithms consist of two partsdividesmaller problems are solved recursively (exceptof coursebase casesconquerthe solution to the original problem is then formed from the solutions to the subproblems traditionallyroutines in which the text contains at least two recursive calls are called divide-and-conquer algorithmswhile routines whose text contains only one recursive call