### Analysis of Algorithms | Asymptotic Notations

#### Analysis of Algorithms :-

In Computer Science, Multiple Algorithms are available to solve a single problem. For example, to sort an array, we have different Algorithms available like Insertion sort, Selection sort, Bubble sort, Quick sort, Merge sort. All these algorithms have different time and space complexities which decides how efficient and fast the Algorithm is.

#### What is Rate of Growth?

The rate at which the running time increases as a function of input is termed as rate of growth.

For example,

n^{4} + n^{2} + 500n + 100 ≈ n^{4}

Above n^{4}, n^{2}, 500n are the individual cost of some function and all get approximated to n^{4 }because n^{4} is the highest rate of growth.

### Commonly used Rate of Growths:-

### Types of Analysis :-

To analyze any algorithm, we need to check on which input it takes less time(performing well) and on which input , it takes long time. As we know, a algorithm is the step by step instruction which can be represented as a series of expression.

To analyze any algorithm, we have three different kinds of notation called asymptotic notation/analysis.

**Worst Case****Best Case****Average Case**

Worst Case defines the input for which the Algorithm takes a longer time. It is given by Omega-Ω Notation. Best Case defines the input for which the Algorithm takes a lowest time. It is given by Big-O Notation. Average Case defines the input for which the Algorithm runs normally assuming that the input is random. It is given by Theta-Θ Notation.

We will look to these 3 notations one by one.

**Big-O Notation**

**Big-O Notation**: This notation gives the tight upper Bound of the given function. It is represented by f(n) = O(g(n)) .

It means that at larger values of n, the upper bound of the given function is g(n).

Big-O Notation has two main Applications :-

- It is used to describe how closely a finite series like Taylor Series approximate a given function.
- It is used in the analysis of Algorithms (for finding the best case).

**Big-O Visualization**

O(g(n)) is set of functions that have smaller or same order of growth . For example O(n^{2}) contains O(1), O(n) and O(nlogn) etc.

**Ques :- Find the upper bound of f(n)= 3n + 8 ?**

Solution :

3n + 8 <= 4n, for all n≥8

Therefore,

3n + 8 = O(n) with c=4 and n_{0}=8

**Ques:- Find the upper bound of f(n)= 2n ^{3} – 2n^{2} ?**

Solution:-

2n^{3} – 2n^{2 }<= 2n^{3 }, for all n ≥1

Therefore,

2n^{3} – 2n^{2} = O(2n^{3}) with c=2 and n_{0}=1

**Omega-Ω Notation**

- This notation gives the tight lower Bound of the given function. It is represented by f(n) = Ω(g(n)) .
- It means that at larger values of n, the lower bound of the given function is g(n).

Omega-Ω Notation has two main Applications :-

- It is used to describe how closely a finite series like Taylor Series approximate a given function.
- It is used in the analysis of Algorithms (for finding the worst case).

### Theta-Θ Notation

Theta-Θ Notation: This notation is used to find the average running time of the Algorithm. This decides whether the upper and lower bound of a function are same or not. If the upper and lower bound are same, then the function have same rate of growth.

Theta-Θ Notation Notation has two main Applications :-

- It is used to describe how closely a finite series like Taylor Series approximate a given function.
- It is used in the analysis of Algorithms (for finding the average case).

CommentsNo comment yet.