The 50% rule refers only to the number of holes and blocks, but not the amounts of memory space taken up by the holes and blocks. The amounts of space depend on the average hole size vs the average block size. If k is the ratio between average hole size and average block size, then the fraction f of space occupied by holes can be determined using the formula f = k/(k + 2). (a) Determine the fraction of space wasted in holes if, on average, an occupied block is twice as large as a hole.
(b) Determine the fraction of space wasted in holes if, on average, a hole is twice as large as an occupied block.