[Introduction] Asymptotic Notations

1. Asymptotic Analysis 

The efficiency of an algorithm depends on the amount of time, storage and other resources required to execute the algorithm. The efficiency is measured with the help of asymptotic notations.With the increase in the input size, the performance will change.

 

Asymptotic notations are the mathematical notations used to describe the running time of an algorithm when the input tends towards a particular value or a limiting value. There are mainly three asymptotic notations :

• Big-O notation
• Omega notation
• Theta notation

 

2. Big-O Notation

Big-O notation represents the upper bound of the running time of an algorithm. Thus, it gives the worst-case complexity of an algorithm.

The above expression can be described as a function f(n) belongs to the set O(g(n)) if there exists a positive c such that it lies between 0 and cg(n), for sufficiently large n. Since it gives the worst-case running time of an algorithm, it is widely used to analyze an algorithm as we are always iterested in the worst-case.

 

3. Omega Notation

Omega notation represents the lower bound of the running time of an algorithm. Thus, it provides the best-case complexity of an algorithm.

 

4. Theta Notation

Theta notation encloses the function from above and below. Since it represents the upper and lower bound of the running time of an algorithm, it is used for analyzing the average-case complexity of an algorithm.

 

5. Master Theorem

The master theorem is a formular for solving recurrence relations of the form :

T(n) = aT(n/b) + f(n),
where,
n = size of input
a = number of subproblems in the recursion
n/b = size of each subproblem. All subproblems are assumed 
     to have the same size.
f(n) = cost of the work done outside the recursive call, 
      which includes the cost of dividing the problem and
      cost of merging the solutions

Here, a ≥ 1 and b > 1 are constants, and f(n) is an asymptotically positive function.

The master theorem is used in calculating the time complexity of recurrence relations (divide and conquer algorithms) in a simple and quick way.

 

If a ≥ 1 and b > 1 are constants and f(n) is an asymptotically positive function, then the time complexity of a recursive relation is given by :

T(n) = aT(n/b) + f(n)

where, T(n) has the following asymptotic bounds:

    1. If f(n) = O(nlogb a-ϵ), then T(n) = Θ(nlogb a).

    2. If f(n) = Θ(nlogb a), then T(n) = Θ(nlogb a * log n).

    3. If f(n) = Ω(nlogb a+ϵ), then T(n) = Θ(f(n)).

ϵ > 0 is a constant.

1. If the cost of solving the sub-problems at each level increase by a certain factor, the value of f(n) will become polynomially smaller than \(n^{log_b a}\). Thus, the time complexity is oppressed by the cost of the last level
2. If the cost of solving the sub-problem at each level is nearly equal, then the value of f(n) will be \(n^{log_b a}\). Thus, the time complexity will be f(n) times the total number of levels ie. \(n^{log_b a} * log n\).
3. If the cost of solving the subproblems at each level decreases by a certain factor, the value of f(n) will become polynomially larger than \(n^{log_b a}\). Thus, the time complexity is oppressed by the cost of f(n).