What Computer Science Studies

Computer science studies computation, not computers. It asks three questions about a procedure: can it be computed at all, how many steps does it take, and how much memory, time and bandwidth does it consume while it runs. The machine is where the answer gets paid for, not what the field is about. The same procedure takes the same number of steps on a phone and on a server, and no amount of hardware rescues a procedure that takes the wrong number.

This book asks one question on every page: what does it cost, and why? Then it answers that question one layer at a time, from the bits in memory to the hard ceiling on what any machine can compute. The reader it is written for already ships code. What it adds is the ability to predict what that code will cost before anyone measures it.

Computation, Not Computers

The object of the field is the algorithm: a precise procedure, independent of any machine or language that runs it. Binary search is binary search in Python, in Go and on paper. Once the procedure is fixed, three questions follow, and this book is organized around them.

The first is what can be computed at all. Some problems have no algorithm, not a slow one and not a clever one, and Chapter 14 shows why. The second is how fast, which is the subject of this chapter and of the structures and algorithms in Chapters 5 to 9. The third is with what resources: memory in Chapter 4, the operating system that hands it out in Chapter 10, and the wire between machines in Chapter 12.

One Algorithm, Many Machines

An algorithm becomes many programs, in many languages, on many machines. What survives every translation is its step count. Finding a name in a sorted list of 2 million entries by halving the list at each look takes about 21 looks. Reading the list from the top takes up to 2 million. That ratio, roughly 100,000 to one, holds on every chip and in every language.

A faster machine changes how long each look takes. It does not change how many looks there are. That is why the algorithm is decided first and the machine second: the machine moves a constant, the algorithm moves the whole curve.

Meet Lantern

Where this book needs one system to make an idea concrete, it uses Lantern. Lantern is the search service of the Millbrook Public Library: 30 branches, 90 self-service kiosks, and a catalogue of 2 million records covering books, audiobooks, films and music. It sits behind the search box on the library's website and on every kiosk. At the Saturday-morning peak it answers about 300 searches a second. It is written in Python and owned by one engineer, Noor.

Lantern appears only where it is the clearest example. A page about two's complement uses an 8-bit number, not a library. But a search service fits nearly every chapter without forcing: the text of titles in dozens of scripts, the index built from hash tables and trees, the ranking, the typo tolerance, the file the index lives in, the workers that serve it, the flaky network the branches report over, and the query language a patron types.

The First Design Question

Every search Lantern answers could be done one of two ways. It could read every record in the catalogue and check whether the patron's words appear in it. Or it could look the words up in an index built in advance, a structure that maps each word straight to the records that contain it.

The first way is correct and simple, and at the peak it means 300 searches a second times 2 million records: 600 million record checks every second. A Python loop manages a few tens of millions of simple steps a second on one core, and checking a record is many steps, not one: on CPython 3.15, testing one record's title, author and subject for a word took about a tenth of a microsecond. At that rate the scan would need sixty to seventy cores doing nothing else. The lookup touches a handful of entries per search and needs a small fraction of one core. No tuning, no faster server and no rewrite in another language closes a gap that size. Only a different algorithm does.

The Ladder Underneath

"Use an index" answers one question and opens the next: why is the index fast? A Python dictionary lookup is fast because it is a hash table, which Chapter 5 takes apart. A hash table is fast because reading one slot of an array is one multiplication and one memory read. That read is fast only if the memory is already in the processor's cache, which is Chapter 4. And the cache exists because main memory is hundreds of times slower than the processor that is waiting for it.

That walk downward is the shape of the whole book. Every "it is fast" has a reason one layer down, and every reason has a limit. The reader who can walk the ladder can say not only that something is fast, but at what size it stops being fast, and why.

The Cost in a System You Run

The endpoint that passes every test on 1,000 rows and times out on 2 million. The nightly job that ran in four minutes last year and seven hours this year. The cloud bill that doubled when traffic grew by half. Each of these was predictable from the procedure before anyone measured it, and each was found in production because nobody asked what the code would cost when the data grew.

This chapter's job is to make that question a habit. The next topic replaces the stopwatch with a count of steps. The one after compresses those counts into Big-O, the shortest honest way to say how cost grows. The rest of the chapter covers what the notation hides: the growth classes that end projects, the difference between an average and a guarantee, and memory as the second price of every algorithm.