Types of Cases for analyzing an algorithm:-

Worst Case
Average Case
Best Case

In Worst Case analysis we usually take the upper bound of the algorithm.

In Average Case analysis, we take the input of all types whether large or small, and calculate the average. However, calculating the average case is not feasible always.

In Best Case analysis the lower bound of the algorithm is analyzed, meaning the minimum running time is calculated.

Asymptotic Notations

What does asymptotic mean?

The word asymptotic means approaching a certain value which could be considered as the limit. The value can range from any finite natural number to an infinite value.

Definition

Asymptotic Notation is used to decide the asymptotic running time of an algorithm, when the input size n is very large, i.e, n-> ∞ . ‘n’ belongs to the set of natural numbers.

Theta Notation (Θ) (Also known as asymptotic tight bound)

This notation is used to determine both the upper bound as well as the lower bound of the algorithm. In other words, this notation determines the minimum and the maximum values until which the algorithm could run.

Θ(g(n)) = {For every, f(n), there exists positive constants c1,c2 and n0.}

Such that 0<= c1.g(n)<=f(n)<=c2.g(n) for all n>=n0.

Big O Notation (O) (Also known as Asymptotic Upper Bound)

This notation is used to determine the asymptotic upper bound of the algorithm. In other words, it is used to know the worst time complexity of the algorithm. This method is highly efficient when the input is as large as 10^9.

O(g(n)) = {For every, f(n) there exist positive constant c and n0 such that 0<=f(n)<=c.g(n) for all n>=n0}

Note:- If f(n)=θ(g(n))
       => f(n)=O(g(n))