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:

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

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

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

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

- 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)

- Plot the graph of the function

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

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

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