1 Starting a fabulous adventure

This chapter introduces the book’s central idea: algorithms are finite procedures for solving problems, and data structures are organized ways of storing information. What makes them “fabulous” is not just correctness, but qualities like tackling real-world problems creatively, producing counterintuitive but powerful results, revealing common patterns across many domains, and making code easier to understand by focusing on meaning rather than low-level mechanics. The chapter also frames the author’s goal of moving beyond standard undergraduate topics into practical and unusual techniques that expand a programmer’s toolkit and sense of discovery.

The chapter then defines complexity as the relationship between problem size and resource cost, especially time and memory, and uses big-O notation to describe common growth rates. It contrasts constant, logarithmic, linear, quasilinear, quadratic, exponential, and factorial behavior, emphasizing how quickly costs can rise as inputs grow. At the same time, it warns that asymptotically better algorithms are not always the best choice in practice, because real performance depends on typical input sizes and actual usage patterns, not just worst-case theory.

As a concrete warmup, the chapter builds an immutable linked list in C# and shows how to reverse it by iterating through the list and pushing items onto a new list. This example highlights both the simplicity and the hidden pitfalls of small designs, including nullable representations, automatically generated equality behavior, and accidental quadratic performance in string concatenation. The chapter closes by previewing the adventures ahead: unusual twists on familiar structures, techniques like persistence and memoization, algorithms used in developer tools, and tools for randomness, probability, and statistical inference.

A graph comparing the growth curves for logarithmic, linear, quasilinear, quadratic, and exponential growth. The logarithmic curve is the shallowest, growing slowly, and the exponential curve is the fastest.

• There are lots of books about standard data structures, such as lists, trees, and hash tables, and the algorithms for sorting and searching them. Lots of implementations of them are already in class libraries. In this book, we’ll look at the less well-known, more off-the-beaten-path data structures and algorithms that I had to learn about during my career. I chose the topics that I found the most fabulous: the ones that are counterintuitive or seemingly magical or that push the boundaries of languages.
• I had to learn about almost all the topics in this book when I needed a new tool in my toolbox to solve a job-related problem. I hope that this book saves you from having to read all the abstruse papers I had to digest if you too have such a problem to solve.
• More important to me, all these fabulous adventures gave me a deeper appreciation for what computer programmers are capable of doing. They changed how I think about the craft of programming. I had a lot of fun along the way, and I hope you do too.
• Asymptotic complexity measures how well a solution scales with the size of the problem you’re throwing at it. You generally want algorithms to be better than quadratic if you want them to scale to large problems.
• Complexity analysis can be subtle. It’s important to remember that time is not the only resource users care about; they might also have opinions about whether avoiding a bad worst-case scenario is more or less important than achieving excellent average performance.
• If problems are always small, asymptotic complexity matters less.
• Reversing a linked list is straightforward if you have an immutable list. Chapter 2 looks at other kinds of immutable lists.

FAQ