Chapter 8

These are the solutions to the .

1. There are a total of 128 I/Os. We can arrive at this either through analyzing the diagram or by plugging the numbers into our Big O expression. Let’s do both!

   At the top level of the diagram, we can see that we take 256 items and load them into main memory. Since each block holds 4 items, this means we’ll have to load a total of 64 blocks since 256/4=64. Since it takes one I/O to load one block, this means we perform 64 I/Os.

   At the next level, we take the same 256 items again (this time, in the form of 4 sublists that each contain 64 items) and load them into memory. As with the top level, this, too, will take 64 I/Os.

   At this point, the algorithm is complete. It comes out that we performed 64+64=128 I/Os.

   We can also plug the numbers into the Big O formula, which is O(N/B log_M/B N/M). In our scenario, this computes to:

   ​	N/B * logM/B N/M =
   ​	(256 / 4) * log16/4 256/16 =
   ​	64 * log4 16 =
   ​	64 * 2 =
   ​	128 I/Os

2. In this case, we can sort all 256 items in 64 I/Os since we only need to engage in one round of Mergesort. To use the Big O formula:

   ​	N/B * logM/B N/M =
   ​	(256 / 4) * (log4 256 / 64) =
   ​	64 * 1 =
   ​	64 I/Os

3. As we’ve seen, Top-Grade Merge takes O(N log₂ K) time. So let’s plug in our numbers:

   ​	N * log2 K =
   ​	1,000,000 * log2 512 =
   ​	9,000,000

   Therefore, there would be a total number of 9,000,000 steps.