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

Post a Comment

Popular posts from this blog

how to cout in cpp

Image
HOW TO COUT IN C++ In this article, you will learn how to cout in CPP  and use of cout in the program with the help of Examples.  In the CPP language displaying things on the console is not a difficult task. First of all build-in library add on the top of the program. The library is used for cout and cin in the cpp language is iostream library. The syntax of the cout in cpp: cout<<" your message "; The universal problem about to print hello world in c++.Here is an example of how to print hello world in cpp. Print hello world #include<iostream> using namespace std; int main() { cout<<" hello world"<<endl; } output: hello world
Read more

Flutter layout

In this blog post, we will explore some of the key concepts and techniques used in Flutter layout and provide examples of how to build a layout for a Flutter application. Widgets and Elements Widgets are the building blocks of a Flutter UI. A widget can be thought of as a self-contained unit of UI, such as a button or a text field. Elements are the instances of widgets that are displayed on the screen. For example, if you have a button widget in your Flutter UI, there will be an element that represents that button on the screen. Layout Widgets Layout widgets are widgets that are specifically designed to control the positioning and sizing of other widgets in a Flutter UI. The most commonly used layout widgets in Flutter are: Container: The Container widget is used to create a rectangular box in a Flutter application. It can be used to add padding, margins, and borders to the widget it contains. Row: The Row widget is used to display a horizontal row of widgets in a Flutter application.
Read more

input by cin in c++

Image
Cin in CPP In this post, we shall learn about how to take input with the help of in the cin and uses it in the CPP language. Taking input in cpp is not a difficult task. The object which is used for taking input in cpp is the cin . The library which is allowed to use the cin object is the iostream. Method for including the iostream library in the program. The syntax is here: #include<iostream> How to take input in c++? CIN  is used for taking any kind of data from the user. The data may be int, float, and char.cin is also used to taking string in the CPP. If someone learns CPP then cin is important to use because it allows to user to interact with your program. The program will be user friendly and generic by using a cin object.
Read more