# Algorithms Summary Points – Part 1: Math and Complexity Classes

This note contains some summary points from my study of algorithms and algorithmic analysis. If you have little or no idea of the concepts I will talk about, this note may not be so helpful to you. I only post these here to serve as a quick reference or as a refresher about these concepts should the need arise. In that case, I suggest you take an advanced course on algorithms and data structures first.  Nevertheless, if you are interested in discussing any of the concepts here I will be glad to be of assistance.

## Math and Complexity Classes

General Induction has the following steps:

1. Basis step – Where we prove that f(n) is true; f(n) is called the induction hypothesis
2. Induction step – Where we assume f(n) and prove f(n+1)

To find the limit of a function (usually fractions), we can either:

1. Simplify using basic algebraic math such as:
2. Factorizing
3. Multiplying the numerator and denominator by the reciprocal of the greatest power of n in the equation.  (Factoring)
4. Find the derivative using calculus.

To tell if a function is increasing, non-decreasing or eventually non-decreasing, we can

1. Take the derivative f’(x) of the function. If for all x in (a, b)
• f'(x) > 0, then the function is increasing on (a, b)
• f’ (x) < 0, then the function is decreasing on (a, b)
2. Plot the graph of the function

The limits for f(n)/g(n) for complexity classes:

1. o = 0 (Zero)
2. Θ = r, where r! = 0
3. O = finite – which means we can find it at all
4. For little-omega, swap f(n) and g(n) in the equation to get little-o to be zero.
5. For big-omega, swap f(n) and g(n) in the equation to get big O to be finite.

Complexity classes definitions

We have 9 common complexity classes as shown below, the first 6 are polynomial time bounded:

Common Complexity Classes