Chapter 2: Getting Started

This chapter will familiarize you with the framework we’ll use throughout the book to think about the design and analysis of algorithms. It is self-contained, but it does include several references to material that will be introduced in Chapters 3 and 4. (It also contains several summations, which Appendix A shows how to solve.)

We’ll begin by examining the insertion sort algorithm to solve the sorting problem introduced in Chapter 1. We’ll specify algorithms using a pseudocode that should be understandable to you if you have done computer programming. We’ll see why insertion sort correctly sorts and analyze its running time. The analysis introduces a notation that describes how running time increases with the number of items to be sorted. Following a discussion of insertion sort, we’ll use a method called divide-and-conquer to develop a sorting algorithm called merge sort. We’ll end with an analysis of merge sort’s running time.