Data Structures, Algorithms, & Applications in C++
Chapter 15, Exercise 27
Suppose that
first fit uses k bins to pack an instance
I that requires a minimum of
b(I) bins.
We may assume that k > 1, because
when k <= 1, we see that
k = b(I).
The sum of the utilized capacity
in the bins 2i - 1 and 2i
exceeds c, because, otherwise,
first fit would have packed all the objects that are
in bin 2i
into bin 2i - 1 and not started
bin 2i, 1 <= i <= k/2.
This means that when k is even,
the sum of the space requirements of the n
objects exceeds (kc)/2. Hence, when
k is even,
b(I) exceeds k/2.
In other words, k < 2b(I).
When k is odd, the sum of the object space requirements
exceeds (k-1)c/2, and so b(I) > (k-1)/2.
Therefore, k < 2b(I) + 1. Since k
and b(I) are integers,
it follows that
k <= 2b(I).