Math Preliminaries in Algorithm Analysis

Algorithm Analysis — Part 2

Welcome back to part two of the Practical Guide to Algorithm Analysis.

Here we will cover the some of the different maths that we’ll need as we go along the series.

So, let’s start with a question: why do we need maths in order to analyse algorithms?

Well, we need maths to distinguish which algorithms are great, which are good, and which are bad; as well as to clearly define the blurred lines that separate them.

We need maths to specifically define an algorithm’s performance. We do this by doing an analysis technique, called priori analysis, which I’m going to show you at depth in the next part of the series.

There are basically two ways to analyse an algorithm:
- the priori estimation of the algorithm (which is a theoretical estimation),
- and the posteriori estimation of the algorithm (which is a practical estimation — more known to as a benchmark).

In a priori estimation, the algorithm’s time/space complexity are computed and analysed before running it as a program.

In a posteriori estimation, the program’s runtime and memory consumption are measured through profiling or benchmarking with a real computer.

Before we dwell unto that matter at depth, let’s first review some of the important maths that we’ll need in the series.

Starting with the laws of exponents:

Logarithm definition:

and its laws:

Logarithm notations that we will be frequently using:

Algebraic expressions:

Factoring:

Arithmetic Series:

Limits:

You don’t really have to memorise every formula written here.

Memorisation is not the point!

The goal is to learn how to analyse and understand algorithms. You can always go back here to review the list of formulas, as a reference.

In Part 3 of this series, we’ll be doing priori estimations on simple algorithms that does nothing!

That’s a start!

That’s all for now.

Cheers!