Algorithms
When you design and analyze algorithms, you need to be able to describe how they
operate and how to design them. You also need some mathematical tools to show
that your algorithms do the right thing and do it efûciently. This part will get you
started. Later parts of this book will build upon this base.
Chapter 1 provides an overview of algorithms and their place in modern computing
systems. This chapter deûnes what an algorithm is and lists some examples.
It also makes a case for considering algorithms as a technology, alongside technologies
such as fast hardware, graphical user interfaces, object-oriented systems,
and networks.
In Chapter 2, we see our ûrst algorithms, which solve the problem of sorting
a sequence of n numbers. They are written in a pseudocode which, although not
directly translatable to any conventional programming language, conveys the structure
of the algorithm clearly enough that you should be able to implement it in the
language of your choice. The sorting algorithms we examine are insertion sort,
which uses an incremental approach, and merge sort, which uses a recursive technique
known as <divide-and-conquer.= Although the time each requires increases
with the value of n, the rate of increase differs between the two algorithms. We
determine these running times in Chapter 2, and we develop a useful <asymptotic=
notation to express them.
Chapter 3 precisely deûnes asymptotic notation. We’ll use asymptotic notation
to bound the growth of functions4most often, functions that describe the running
time of algorithms4from above and below. The chapter starts by informally deûning
the most commonly used asymptotic notations and giving an example of how to
apply them. It then formally deûnes ûve asymptotic notations and presents conventions
for how to put them together. The rest of Chapter 3 is primarily a presentation
of mathematical notation, more to ensure that your use of notation matches that in
this book than to teach you new mathematical concepts.