Aysmptotic notation

 Asymptotic notation:

In this article, we will learn about the Asymptotic notation: Big o notation, theta notation, and omega notation. 


Asymptotic notations are the mathematical notations used to analyze the efficiency and effectiveness of the algorithm. The efficiency of the algorithm depends on the storage, amount of time, and many other factors.


The algorithm does not have the same performance on different inputs. The performance change with the input.



Why used asymptotic notations:


The comparison of the algorithms is very important in the computer science world. There are a lot of algorithms but we want to choose the best one. The comparison of the algorithms is done by the asymptotic notations.



let’s take an example of sorting, there are a lot of algorithms of the sorting selection sort, bubble sort, and merge sort,etc.we can use the best algorithm by the help of the asymptotic notations.


Big o Notation:


This tells about the worst case of the algorithm and the upper bound of the algorithms. At last,limit of the algorithm find by the big o .lets understand from the following graph.


asymptotic-notation


In the vertical, time is shown, and horizontally the number of inputs of the algorithm.

c(g(n)) greater than or equal to the f(n), there exist c is a positive number for all n=k,k greater than zero. The big o tells the maximum time required for the algorithm o(g(n)).


Always, we want to know the worst case of the algorithm that's why big o notation widely used.

Big omega notation:


The big omega tells about the best case of the algorithms and lowers the bound of the running time of the algorithms. The big omega provides the best limit of the algorithms.. let's understand big omega from the following graph



        
asymptotic-notation

f(n)greater than or equal to the c(g(n)), there exist c is a positive number for all n=k,k greater than zero. The omega tells the minimum time required for the algorithmΩ(g(n))




Theta notation:


The theta lies between the upper and lower limit of the algorithms. The average case is handle by the theta. It is used to analyze the average complexity of the algorithms.

asymptotic-notation

c2(g(n)) is greater than or equal to the f(n)greater than or equal to the c1(g(n)) , there exist c1,c2 are  positive numbers for all n=k,k greater than zero.

The f(n) function lies between the c1(g(n)) and c2(g(n)).


The theta tells about the average time taken by the algorithm(Θ-notation)


Please write the comment, if you find anything incorrect and any problem in the above topic or you want to share more information about the above topic.

Comments

Hire a programmer

Popular posts from this blog

CSS selector

C program to convert decimal to binary number

C Program to convert binary to decimal number