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

Diferrence between flutter and react native

In the world of mobile app development, there are two popular frameworks that have gained significant traction in recent years: Flutter and React Native. Both these frameworks allow developers to build high-performance, cross-platform mobile applications. However, there are some fundamental differences between the two that developers should be aware of when choosing which one to use. Flutter: Flutter is an open-source mobile application development framework created by Google. It was launched in 2017 and has quickly become one of the most popular mobile development frameworks, especially for building beautiful and high-performance mobile applications with a single codebase. Flutter uses the Dart programming language, which is also developed by Google. Pros of flutter: Flutter provides a rich set of customizable widgets that allow developers to create stunning and responsive UI designs. Flutter offers a "hot reload" feature, which allows developers to see the changes in their ...
Read more

Flutter Widgets

Flutter is an open-source UI toolkit for building natively compiled applications for mobile, web, and desktop from a single codebase. One of the key features of Flutter is its rich set of widgets, which enable developers to build beautiful and responsive user interfaces for their applications. In this blog post, we will explore some of the most commonly used widgets in Flutter and provide examples of how they can be used to build engaging and user-friendly interfaces. Text Widget The Text widget is used to display text in a Flutter application. It allows developers to customize the font size, color, and style of the text. Here is an example of how to use the Text widget: dart: Text( 'Hello, world!', style: TextStyle( fontSize: 20.0, fontWeight: FontWeight.bold, color: Colors.blue, ), ) Image Widget The Image widget is used to display images in a Flutter application. It supports a variety of image formats, including JPEG, PNG, and GIF. Here is an example of how...
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