Algorithm complexity

Before we start with the dirty (and fun) job of improving program speed, I’d like to present a bit of computer science theory, namely, Big O notation.

You don’t have to worry, I will not use pages of mathematical formulas and talk about infinitesimal asymptotes. Instead, I will just present the essence of Big O notation, the parts that are important to every programmer.

In the literature and, of course, on the web, you will see expressions such as O(n), O(n^2), O(1), and similar. This fancy-looking notation hides a really simple story. It tells us how much slower the algorithm will become if we increase the data size by a factor of n.

Information

The n^2 notation means “n to the power of two,” or n2. This notation is frequently used on the internet because it can be written with standard ASCII characters. This book uses the more readable variant, O(n2).

Let’s say we have an algorithm with a complexity of O(n), which...