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