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

Leave a Reply

Your email address will not be published. Required fields are marked *