Count I/Os, Not Steps

Because of the slowness of I/Os, when it comes to algorithms that involve I/Os, computer scientists like to measure time complexity differently than they do with “regular” non-I/O algorithms. Specifically, instead of counting how many steps the algorithm takes, we count the number of I/Os the algorithm performs.

This line of thinking is driven by how much slower I/Os are when compared with main-memory steps. If an algorithm has 5 I/Os plus 300 main-memory steps, the 5 I/Os are so much slower than the 300 main-memory steps. Therefore, we simply ignore the main-memory steps altogether.

This is a bit similar to what I discussed back in Volume 1, Chapter 6, namely, that when we have an algorithm with N⁴+N³+N²+N steps, we only keep the highest order and simply say that the algorithm is O(N⁴). I explained that this is because when compared with N⁴, all the lower orders of N are insignificant.

The same basic idea holds true here as well. When our algorithm includes both I/Os plus main-memory steps together, we only count how many I/Os there are since the main-memory steps are insignificant by comparison.

Big O of I/O

In Volume 1, Chapter 3, I explained that Big O notation is valuable because it effectively describes the time complexity of any algorithm, irrespective of how much data the algorithm is processing. Instead of saying that a particular algorithm takes 10 steps for 10 data elements and 1,000 steps for 1,000 data elements, we simply say that the algorithm has a speed of O(N), with N signifying how much data we’re dealing with.

But to adapt Big O Notation to external-memory algorithms, we need to switch what it is that Big O measures. Specifically, we will adapt Big O Notation so it tells us how many I/Os the algorithm performs when there are N elements.

Let me break this down.

As mentioned, for “regular” algorithms, the term O(N) says that for N data elements, the algorithm takes N steps. But for external-memory algorithms, we’d want O(N) to mean that for N data elements, the algorithm performs N I/Os.

But here’s the thing. Let’s return to our earlier algorithm in which we compute the sum of all the integers in a list. If all the integers were in RAM, the algorithm would indeed be O(N) since for the N integers, the algorithm takes N steps.

But is this true for the external-memory version of summing integers? Is it accurate to say that for N integers, the algorithm performs N I/Os?

Indeed, this is not the case. We saw in our visual example that when there are 9 integers, our algorithm performed only 3 I/Os. So how do we use Big O to tell us how many I/Os the algorithm performs when there are N elements?

If you can resist the temptation to read further immediately, I recommend you first take a moment to ponder this and try to come up with your own answer.

Okay, let’s analyze this thing.

The key to everything lies in the computer’s block size. I mentioned earlier that each computer, based on its own particular hardware specs, has a particular block size. If there are 10 pieces of data, and the block size is 2, we know that it will take 5 I/Os to process all the data. In other words, because each I/O transfers a single block from the filesystem to main memory, it’ll take 5 I/Os to transfer all the blocks of size 2 until all 10 pieces of data are transferred.

If we want to express this using math, we’d say:

To express this same idea in terms of N pieces of data, we’d say that:

To make this notation a bit more concise, computer scientists like to use the variable “B” to refer to the block size. So, to express the previous formula using this shiny new variable, we’d say:

There’s potential to get confused regarding B, so let me make this abundantly clear: B stands for block size, and not the number of blocks. It’s easy to mix that up, so go ahead and repeat this factoid 10 times before moving on.

With this, we’ve now unlocked the ability to express the number of I/Os relative to N. That is, for N data elements, an algorithm will perform N/B I/Os.

We can now answer our original question of how we can use Big O to describe the time complexity of summing all the integers in a file. We’d say that it takes:

O(N/B) I/Os.

This is the Big O way to express that for N data elements, the algorithm will execute N/B I/Os.

Finding Duplicates

Let’s look at another instance where we can apply Big O notation to I/Os.

Say that we have an array of strings, and we want to see if we can find any duplicate strings. Throughout Volume 1 (and especially in Chapter 19), I laid out both fast and slow ways of doing this.

The slowest approach is to apply brute force: for each string, check all the other strings to see if we get a match. In a “regular” case, where our array of strings is small enough to fit inside main memory, the speed of this approach would be described as O(N²). This is because for each of the N strings, we have to check N strings.

But now imagine that our list of strings is so large that it cannot fit in RAM and can only be stored as a humongous file in the filesystem. How would we describe the speed of our brute-force algorithm now? To figure this out, the first thing we need to do is determine what I/Os the algorithm would need to perform. After doing that, we can then count how many I/Os the algorithm performs in total.

We know that the computer will virtually divide the data into blocks and perform an I/O each time to load a block into main memory. To access even the first string in our file, the computer will need to transfer the first block into memory.

Let’s say that the first string in our file is "apple". This means that we want to search the rest of our list to see if there’s another instance of "apple". Now, because we happen to have the first block in memory, we may as well search that block for another "apple". If there is no such matching string in the first block, the computer must now go to the filesystem again and perform a second I/O to load the next block into memory.

Eventually, the computer will load the entire file one block at a time, assuming it doesn’t find a duplicate before getting to the end of the file. Because there are N strings in the file, we’d say that the computer performs N/B I/Os to perform a search for the duplicate "apple". Now, keep in mind that we’ve only so far dealt with the search for "apple"! In a worst-case scenario, where the list doesn’t contain any duplicates, we need to repeat the same approach for each and every string in our file.

And so, the algorithm must ultimately perform N/B I/Os for each of the N strings. This is N/B * N, which is equivalent to N²/B. As such, Big O notation would describe this as O(N²/B).

The main takeaway from this section is that we’ve discovered the preferred approach for measuring the time complexity of external-memory algorithms. In a nutshell, it all boils down to counting I/Os rather than counting main-memory steps.

It’s certainly great to be armed with this knowledge, but you haven’t yet seen how it might dictate the way you should write our code. But that’s all about to change now. In the next section, you’ll see that some external-memory algorithms can be written in multiple ways and that we’ll need Big O to help us determine which approach is fastest.