Summary

In this chapter, you saw how we can think about measuring the running time of and the memory required by an algorithm in seconds and bytes, respectively. Since this depends on the particular implementation, the programming platform, and the hardware, we need a notion of talking about running time in an abstract way. Asymptotic complexity is a measure of the growth of a function when the input is very large. We can use it to abstract our discussion on running time. This is not to say that a programmer should not spend any time to make a run a program twice as fast, but that comes only after the program is already running at the minimum asymptotic complexity.

We also saw that the asymptotic complexity is not just a property of the problem at hand that we are trying to solve, but also a property of the particular way we are solving it, that is, the particular algorithm we are using. We also saw that two programs solving the same problem while running different algorithms with different asymptotic complexities can perform vastly differently for large inputs. This should be enough motivation to study algorithms explicitly.

In the following chapters, we will study the most used algorithmic tricks and concepts required in daily use. We will start from the very easy ones that are also the building blocks for the more advanced techniques. This book is, of course, by no means comprehensive; the objective is to provide enough background to make you comfortable with the basic concepts and then you can read on.