Learn: What are **Asymptotic Notations?** How they are used to express the time complexity of algorithm?

Submitted by Abhishek Jain, on July 27, 2017

**Asymptotic notation** employs the following notations to express the time complexity of algorithms. These are termed **asymptotic notation** since they are meaningful approximations of functions that represent the time or space complexity of a program.

The **asymptotic notation** is nothing but to assume the value of a function. In this notation the complexity is usually expressed in the form of a function **f(n)** , where **'n'** is the input size for a given instance of the problem being solved.

**The most commonly used asymptotic notations are:**

**Big O** is the formal method of expressing time complexity in terms of the upper bound value of an algorithms running time. It’s a measure of the longest amount of time it could possibly take for the algorithm to complete.

**Definition:** f(n)=O(g(n))

If there are two positive constants **c** and **n _{0}** such that

|f(n)|<= c|g(n)| for all n >= n_{0}

Based on **Big O notation**, the algorithms can be categorized as follows:

- Constant running time algorithms: Algorithms reporting
**O(1)**time complexity. - Logarithmic time algorithms:
**O(logn)**time complexity is referred to as logarithmic. - Linear time algorithms: The time complexities of
**O(n)**are called lineartime complexities. - Polynomial time algorithms: In general , time complexities of the type
**O(n**are called polynomial time complexities.^{k}) - Exponential time algorithms: Time complexities such as
**O(2**,^{n})**O(3**, in general^{n})**O(k**are called as exponential time complexities.^{n})

**Some of the commonly occurring time complexities in their ascending orders of magnitude are listed below:**

O(1) <= O(log n) <= O(n) <= O(n.log n) <= O(n2) <= O(n3) <= O(2n)

**Example:**

f(n) | g(n) | |
---|---|---|

1) 16n^{3}+78n^{2}+12n |
n^{3} |
f(n)=O(n^{3}) |

2) 34n – 90 | N | f(n)=O(n) |

3) 56 | 1 | f(n)=O(1) |

Here, **g(n)** is the upper bound of the function **f(n)**.

The **asymptotic notation** used to denote space or time complexity in terms of lower bound value is called as **Big Omega notation**.

**Definition:** f(n)= Ω(g(n))

If there are two positive constants **c** and **n _{0}** such that

|f(n)|>= c|g(n)| for all n >= n_{0}

**Example:**

f(n) | g(n) | |
---|---|---|

1) 16n^{3}+8n^{2}+2 |
n^{3} |
f(n)=Ω(n^{3}) |

2) 24n + 9 | N | f(n)= Ω (n) |

Here, **g(n)** is the lower bound of the function **f(n)**.

**The asymptotic notation** used to denote space or time complexity in terms of tight bound value is called as Big Theta (θ) Notation.These requires both Big O and Omega (Ω), so that’s why it’s referred to as a tight bound (it must be both the upper and lower bound).

**Definition:** f(n)=θ (g(n))

If there are two positive constants c_{1,c2} and n_{0} such that

c_{1}|g(n)| <= |f(n)|<= c_{2}|g(n)| for all n >= n_{0}

**Example:**

f(n) | g(n) | |
---|---|---|

1) 28n + 9 | N | f(n)= θ (n) since f(n)> 28n and f(n) <= 37n for n >=1 |

2) 16n^{2}+30n-90 |
n^{2} |
f(n)= θ (n^{2}) |

3) 7.2^{n} + 30n |
2^{n} |
f(n)= θ (2^{n}) |

From the definition it implies that the function **g(n)** is both an upper bound and a lower bound for the function **f(n)** for all values of **n**, **n>=n _{0}**. This means that

Reference: http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/intro.htm

Are you a blogger? Join our Blogging forum.

Comments and Discussions

.resCodeAS1 { display: block; width: 320px; height: 50px; }
@media(min-width: 300px) { .resCodeAS1 { display: none; } }
@media(min-width: 480px) { .resCodeAS1 { display: none; } }
@media(min-width: 750px) { .resCodeAS1 { display: block; width: 336px; height: 280px; } }
(adsbygoogle = window.adsbygoogle || []).push({});

(adsbygoogle = window.adsbygoogle || []).push({});

(adsbygoogle = window.adsbygoogle || []).push({});

solved programs: » C » C++ » DS » Java » C# |

aptitude que. & ans.: » C » C++ » Java » DBMS |

interview que. & ans.: » C » Embedded C » Java » SEO » HR |

close Like other websites, this site uses cookies to deliver relevant ads based on your interest, by using our website, you acknowledge that you have read our privacy policy.