# Asymptotic Analysis

#### In this tutorial, you will learn what asymptotic notations are. Also, you will learn about Big-O notation, Theta notation and Omega notation.

The efficiency of an algorithm depends on the amount of time, storage and other resources required to execute the algorithm. The efficiency is measured with the help of asymptotic notations.

An algorithm may not have the same performance for different types of inputs. With the increase in the input size, the performance will change.

The study of change in performance of the algorithm with the change in the order of the input size is defined as asymptotic analysis.

## Asymptotic Notations

Asymptotic notations are the mathematical notations used to describe the running time of an algorithm when the input tends towards a particular value or a limiting value.

For example: In bubble sort, when the input array is already sorted, the time taken by the algorithm is linear i.e. the best case.

But, when the input array is in reverse condition, the algorithm takes the maximum time (quadratic) to sort the elements i.e. the worst case.

When the input array is neither sorted nor in reverse order, then it takes average time. These durations are denoted using asymptotic notations.

There are mainly three asymptotic notations: Theta notation, Omega notation and Big-O notation.

## Theta Notation (Θ-notation)

Theta notation encloses the function from above and below. Since it represents the upper and the lower bound of the running time of an algorithm, it is used for analyzing the average case complexity of an algorithm.

For a function `g(n)`

, `Θ(g(n))`

is given by the relation:

Θ(g(n)) = { f(n): there exist positive constants c_{1}, c_{2}and n_{0}such that 0 ≤ c_{1}g(n) ≤ f(n) ≤ c_{2}g(n) for all n ≥ n_{0}}

The above expression can be described as a function `f(n)`

belongs to the set `Θ(g(n))`

if there exist positive constants `c`

and _{1}`c`

such that it can be sandwiched between _{2}`c`

and _{1}g(n)`c`

, for sufficiently large n._{2}g(n)

If a function `f(n)`

lies anywhere in between `c`

and _{1}g(n)`c`

for all _{2}g(n)`n ≥ n0`

, then `f(n)`

is said to be asymptotically tight bound.

## Big-O Notation (O-notation)

Big-O notation represents the upper bound of the running time of an algorithm. Thus, it gives the worst case complexity of an algorithm.

O(g(n)) = { f(n): there exist positive constants c and n_{0}such that 0 ≤ f(n) ≤ cg(n) for all n ≥ n_{0}}

The above expression can be described as a function `f(n)`

belongs to the set `O(g(n))`

if there exists a positive constant `c`

such that it lies between `0`

and `cg(n)`

, for sufficiently large `n`

.

For any value of `n`

, the running time of an algorithm does not cross time provided by `O(g(n))`

.

Since it gives the worst case running time of an algorithm, it is widely used to analyze an algorithm as we are always interested in the worst case scenario.

## Omega Notation (Ω-notation)

Omega notation represents the lower bound of the running time of an algorithm. Thus, it provides best case complexity of an algorithm.

Ω(g(n)) = { f(n): there exist positive constants c and n_{0}such that 0 ≤ cg(n) ≤ f(n) for all n ≥ n_{0}}

The above expression can be described as a function `f(n)`

belongs to the set `Ω(g(n))`

if there exists a positive constant `c`

such that it lies above `cg(n)`

, for sufficiently large `n`

.

For any value of `n`

, the minimum time required by the algorithm is given by Omega `Ω(g(n))`

.

# Python Example for Beginners

## Two Machine Learning Fields

There are two sides to machine learning:

**Practical Machine Learning:**This is about querying databases, cleaning data, writing scripts to transform data and gluing algorithm and libraries together and writing custom code to squeeze reliable answers from data to satisfy difficult and ill defined questions. It’s the mess of reality.**Theoretical Machine Learning**: This is about math and abstraction and idealized scenarios and limits and beauty and informing what is possible. It is a whole lot neater and cleaner and removed from the mess of reality.

**Data Science Resources: Data Science Recipes and Applied Machine Learning Recipes**

**Introduction to Applied Machine Learning & Data Science for Beginners, Business Analysts, Students, Researchers and Freelancers with Python & R Codes @ Western Australian Center for Applied Machine Learning & Data Science (WACAMLDS) !!!**

Latest end-to-end Learn by Coding Recipes in Project-Based Learning:

**Applied Statistics with R for Beginners and Business Professionals**

**Data Science and Machine Learning Projects in Python: Tabular Data Analytics**

**Data Science and Machine Learning Projects in R: Tabular Data Analytics**

**Python Machine Learning & Data Science Recipes: Learn by Coding**

**R Machine Learning & Data Science Recipes: Learn by Coding**

**Comparing Different Machine Learning Algorithms in Python for Classification (FREE)**

Disclaimer: The information and code presented within this recipe/tutorial is only for educational and coaching purposes for beginners and developers. Anyone can practice and apply the recipe/tutorial presented here, but the reader is taking full responsibility for his/her actions. The author (content curator) of this recipe (code / program) has made every effort to ensure the accuracy of the information was correct at time of publication. The author (content curator) does not assume and hereby disclaims any liability to any party for any loss, damage, or disruption caused by errors or omissions, whether such errors or omissions result from accident, negligence, or any other cause.The information presented here could also be found in public knowledge domains.