# Asymptotic Notations

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:**

## 1) Big O Notation

**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)**.

## 2) Big Omega(Ω) Notation

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)**.

### 3) Big Theta(θ) Notation

**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

**f(n)**is such that ,

**f(n)= O(g(n))**and

**f(n)= Ω(g(n))**.

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

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions