# Examples on Asymptotic Notation – Upper, Lower and Tight Bound

In this article, we will discuss some examples on asymptotic notation and mathematics behind it.

## Finding upper bound

Upper bound of any function is defined as follow:

Let f(n) and g(n) are two nonnegative functions indicating the running time of two algorithms. We say, g(n) is upper bound of f(n) if there exist some positive constants c and n

_{0}such that 0 ≤ f(n) ≤ c.g(n) for all n ≥ n_{0}. It is denoted as f(n) = Ο(g(n)).

### Examples on Upper Bound Asymptotic Notation

**Example:** Find upper bound of running time of constant function f(n) = 6993.

To find the upper bound of f(n), we have to find c and n_{0} such that 0 ≤ f (n) ≤ c.g(n) for all n ≥ n_{0}

0 ≤ f (n) ≤ c × g (n)

0 ≤ 6993 ≤ c × g (n)

0 ≤ 6993 ≤ 6993 x 1

So, c = 6993 and g(n) = 1

Any value of c which is greater than 6993, satisfies the above inequalities, so all such values of c are possible.

0 ≤ 6993 ≤ 8000 x 1 → true

0 ≤ 6993 ≤ 10500 x 1 → true

Function f(n) is constant, so it does not depend on problem size n. So n_{0}= 1

f(n) = O(g(n)) = O(1) for c = 6993, n_{0} = 1

f(n) = O(g(n)) = O(1) for c = 8000, n_{0} = 1 and so on.

**Example:** Find upper bound of running time of a linear function f(n) = 6n + 3.

To find upper bound of f(n), we have to find c and n_{0} such that 0 ≤ f (n) ≤ c × g (n) for all n ≥ n_{0}

0 ≤ f (n) ≤ c × g (n)

0 ≤ 6n + 3 ≤ c × g (n)

0 ≤ 6n + 3 ≤ 6n + 3n, for all n ≥ 1 (There can be such infinite possibilities)

0 ≤ 6n + 3 ≤ 9n

So, c = 9 and g (n) = n, n_{0} = 1

**Tabular Approach**

0 ≤ 6n + 3 ≤ c × g (n)

0 ≤ 6n + 3 ≤ 7 n

Now, manually find out the proper n_{0}, such that f (n) ≤ c.g (n)

n | f(n) = 6n + 3 | c.g(n) = 7n |

1 | 9 | 7 |

2 | 15 | 14 |

3 | 21 | 21 |

4 | 27 | 28 |

5 | 33 | 35 |

From Table, for n ≥ 3, f (n) ≤ c × g (n) holds true. So, c = 7, g(n) = n and n_{0} = 3, There can be such multiple pair of (c, n_{0})

f(n) = O(g(n)) = O(n) for c = 9, n_{0} = 1

f(n) = O(g(n)) = O(n) for c = 7, n_{0} = 3

and so on.

**Example: **Find upper bound of running time of quadratic function f(n) = 3n^{2} + 2n + 4.

To find upper bound of f(n), we have to find c and n_{0} such that 0 ≤ f (n) ≤ c × g (n) for all n ≥ n_{0}

0 ≤ f (n) ≤ c × g (n)

0 ≤ 3n^{2} + 2n + 4 ≤ c × g (n)

0 ≤ 3n^{2} + 2n + 4 ≤ 3n^{2 }+ 2n^{2} + 4n^{2},

for all n ≥ 1:

0 ≤ 3n^{2} + 2n + 4 ≤ 9n^{2}

0 ≤ 3n^{2} +2n + 4 ≤ 9n^{2}

So, c = 9, g(n) = n^{2} and n_{0} = 1

**Tabular approach**:

0 ≤ 3n^{2} + 2n + 4 ≤ c.g (n)

0 ≤ 3n^{2 }+ 2n + 4 ≤ 4n^{2}

Now, manually find out the proper n_{0}, such that f(n) ≤ c.g(n)

n | f(n) = 3n^{2} + 2n + 4 | c.g (n) = 4n^{2} |

1 | 9 | 4 |

2 | 20 | 16 |

3 | 37 | 36 |

4 | 60 | 64 |

5 | 89 | 100 |

From Table, for n ≥ 4, f(n) ≤ c × g (n) holds true. So, c = 4, g(n) = n^{2} and n_{0} = 4. There can be such multiple pair of (c, n_{0})

f(n) = O (g(n)) = O (n^{2}) for c = 9, n_{0} = 1

f(n) = O (g(n)) = O (n^{2}) for c = 4, n_{0} = 4

and so on.

**Example: **Find upper bound of running time of a cubic function f(n) = 2n^{3 }+ 4n + 5.

To find upper bound of f(n), we have to find c and n_{0} such that 0 ≤ f(n) ≤ c × g(n) for all n ≥ n_{0}

0 ≤ f(n) ≤ c.g(n)

0 ≤ 2n^{3} + 4n + 5 ≤ c **×** g(n)

0 ≤ 2n^{3 }+ 4n + 5 ≤ 2n^{3}+ 4n^{3} + 5n^{3}, for all n ³ 1

0 ≤ 2n^{3 }+ 4n + 5 ≤ 11n^{2}

So, c = 11, g(n) = n^{3} and n_{0} = 1

Tabular approach

0 ≤ 2n^{3} + 4n + 5 ≤ c **× **g(n)

0 ≤ 2n^{3 }+ 4n + 5 ≤ 3n^{3}

Now, manually find out the proper n_{0}, such that f(n) ≤ c **× **g(n)

n | f(n) = 2n^{3} + 4n + 5 | c.g(n) = 3n^{3} |

1 | 11 | 3 |

2 | 29 | 24 |

3 | 71 | 81 |

4 | 149 | 192 |

From Table, for n ≥ 3, f(n) ≤ c **× **g(n) holds true. So, c = 3, g(n) = n^{3} and n_{0} = 3. There can be such multiple pair of (c, n_{0})

f(n) = O(g(n)) = O(n^{3}) for c = 11, n_{0} = 1

f(n) = O(g(n)) = O(n^{3}) for c =3, n_{0} = 3 and so on.

## Lower Bound

Lower bound of any function is defined as follow:

Let f(n) and g(n) are two nonnegative functions indicating the running time of two algorithms. We say the function g(n) is lower bound of function f(n) if there exist some positive constants c and n

_{0}such that 0 ≤ c.g(n) ≤ f(n) for all n ≥ n_{0}. It is denoted as f(n) = Ω (g(n)).

### Examples on Lower Bound Asymptotic Notation

**Example: **Find lower bound of running time of constant function f(n) = 23.

To find lower bound of f(n), we have to find c and n_{0} such that { 0 ≤ c **× **g(n) ≤ f(n) for all n ≥ n_{0 }}

0 ≤ c **×** g(n) ≤ f(n)

0 ≤ c **×** g(n) ≤ 23

0 ≤ 23.1 ≤ 23 → true

0 ≤ 12.1 ≤ 23 → true

0 ≤ 5.1 ≤ 23 → true

Above all three inequalities are true and there exists such infinite inequalities

So c = 23, c = 12, c = 5 and g(n) = 1. Any value of c which is less than or equals to 23, satisfies the above inequality, so all such value of c are possible. Function f(n) is constant, so it does not depend on problem size n. Hence n_{0} = 1

f(n) = Ω (g(n)) = Ω (1) for c = 23, n_{0} = 1

f(n) = Ω (g(n)) = Ω (1) for c = 12, n_{0} = 1 and so on.

**Example: ** Find lower bound of running time of a linear function f(n) = 6n + 3.

To find lower bound of f(n), we have to find c and n_{0} such that 0 ≤ c.g(n) ≤ f(n) for all n ≥ n_{0}

0 ≤ c **× **g(n) ≤ f(n)

0 ≤ c **×** g(n) ≤ 6n + 3

0 ≤ 6n ≤ 6n + 3 → true, for all n ≥ n_{0}

0 ≤ 5n ≤ 6n + 3 → true, for all n ≥ n_{0}

Above both inequalities are true and there exists such infinite inequalities. So,

f(n) = Ω (g(n)) = Ω (n) for c = 6, n_{0} = 1

f(n) = Ω (g(n)) = Ω (n) for c = 5, n_{0} = 1

and so on.

**Example:** Find lower bound of running time of quadratic function f(n) = 3n^{2} + 2n + 4.

To find lower bound of f(n), we have to find c and n_{0} such that 0 ≤ c.g(n) ≤ f(n) for all n ³ n_{0}

0 ≤ c **× **g(n) ≤ f(n)

0 ≤ c **× **g(n) ≤ 3n^{2} + 2n + 4

0 ≤ 3n^{2} ≤ 3n^{2} + 2n + 4, → true, for all n ≥ 1

0 ≤ n^{2} ≤ 3n^{2} + 2n + 4, → true, for all n ≥ 1

Above both inequalities are true and there exists such infinite inequalities.

So, f(n) = Ω (g(n)) = Ω (n^{2}) for c = 3, n_{0} = 1

f(n) = Ω (g(n)) = Ω (n^{2}) for c = 1, n_{0} = 1

and so on.

**Example:** Find lower bound of running time of quadratic function f(n) = 2n^{3} + 4n + 5.

To find lower bound of f(n), we have to find c and n_{0} such that 0 ≤ c.g(n) ≤ f(n) for all n ≥ n_{0}

0 ≤ c **× **g (n) ≤ f(n)

0 ≤ c **× **g (n) ≤ 2n^{3 }+ 4n + 5

0 ≤ 2n^{3 }≤ 2n^{3 }+ 4n + 5 → true, for all n ≥ 1

0 ≤ n^{3} ≤ 2n^{3 }+ 4n + 5 → true, for all n ≥ 1

Above both inequalities are true and there exists such infinite inequalities.

So, f(n) = Ω (g(n)) = Ω (n^{3}) for c = 2, n_{0} = 1

f(n) = Ω (g(n)) = Ω (n^{3}) for c = 1, n_{0} = 1

and so on.

## Tight Bound

Tight bound of any function is defined as follow:

Let f(n) and g(n) are two nonnegative functions indicating running time of two algorithms. We say the function g(n) is tight bound of function f(n) if there exist some 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}. It is denoted as f(n) = Θ (g(n)).

### Examples on Tight Bound Asymptotic Notation:

**Example:** Find tight bound of running time of constant function f(n) = 23.

To find tight bound of f(n), we have to find 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}

0 ≤ c_{1}**×** g(n) ≤ 23 ≤ c_{2 }**× **g(n)

0 ≤ 22 **×**1 ≤ 23 ≤ 24 **× **1, → true for all n ≥ 1

0 ≤ 10 **×**1 ≤ 23 ≤ 50 **×** 1, → true for all n ≥ 1

Above both inequalities are true and there exists such infinite inequalities.

So, (c_{1}, c_{2}) = (22, 24) and g(n) = 1, for all n ≥ 1

(c_{1}, c_{2}) = (10, 50) and g(n) = 1, for all n ≥ 1

f(n) = Θ (g (n)) = Θ (1) for c_{1} = 22, c_{2} = 24, n_{0} = 1

f(n) = Θ (g (n)) = Θ (1) for c_{1} = 10, c_{2} = 50, n_{0} = 1

and so on.

**Example:** Find tight bound of running time of a linear function f(n) = 6n + 3.

To find tight bound of f(n), we have to find 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}

0 ≤ c_{1}**×** g(n) ≤ 6n + 3 ≤ c_{2 }**×**** **g(n)

0 ≤ 5n ≤ 6n + 3 ≤ 9n, for all n ≥ 1

Above inequality is true and there exists such infinite inequalities.

So, f(n) = Θ(g(n)) = Θ(n) for c_{1} = 5, c_{2} = 9, n_{0} = 1

**Example:** Find tight bound of running time of quadratic function f(n) = 3n^{2} + 2n + 4.

To find tight bound of f(n), we have to find 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}

0 ≤ c_{1 }**×** g(n) ≤ 3n^{2 }+ 2n + 4 ≤ c_{2 }**×** g(n)

0 ≤ 3n^{2} ≤ 3n^{2} + 2n + 4 ≤ 9n^{2}, for all n ≥ 1

Above inequality is true and there exists such infinite inequalities. So,

f(n) = Θ(g(n)) = Θ(n^{2}) for c_{1} = 3, c_{2} = 9, n_{0} = 1

**Example:** Find tight bound of running time of a cubic function f(n) = 2n^{3} + 4n + 5.

To find tight bound of f(n), we have to find 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}

0 ≤ c_{1 }**×** g(n) ≤ 2n^{3 }+ 4n + 5 ≤ c_{2 }**×** g(n)

0 ≤ 2n^{3 }≤ 2n^{3 }+ 4n + 5 ≤ 11n^{3}, for all n ≥ 1

Above inequality is true and there exists such infinite inequalities. So,

f(n) = Θ(g(n)) = Θ(n^{3}) for c_{1} = 2, c_{2} = 11, n_{0} = 1

## General Problems

**Example: **Show that : (i) 3n + 2 = Θ(n) (ii) 6*2^{n} + n^{2} = Θ(2^{n})

(i) 3n + 2 = Θ(n)

To prove above statement, we have to find 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}

0 ≤ c_{1}**×** g(n) ≤ 3n + 2 ≤ c_{2 }**×**** **g(n)

0 ≤ 2n ≤ 3n + 2 ≤ 5n, for all n ≥ 1

So, f(n) = Θ(g(n)) = Θ(n) for c_{1} = 2, c_{2} = 5 n_{0} = 1

(ii) 6*2^{n} + n^{2} = Θ(2^{n})

To prove above statement, we have to find 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}

0 ≤ c_{1}**×** g(n) ≤ 6*2^{n} + n^{2} ≤ c_{2 }**×** g(n)

0 ≤ 6.2^{n} ≤ 6*2^{n} + n^{2} ≤ 7*2^{n}, for all n ≥ 1

So, f(n) = Θ(g(n)) = Θ(2^{n}) for c_{1} = 6, c_{2} = 7 n_{0} = 1

**Example: **Let f(n) and g(n) be asymptotically positive functions. Prove or disprove following. f(n) + g(n) = q(min(f(n), g(n))).

Function f(n) and g(n) are non-negative functions such that there exist f(n) ≥ 0 and g(n) ≥ 0, for all n ≥ n_{0}.

For all such n ≥ n_{0}, f(n) + g(n) ≥ f(n) ≥ 0

Similarly, f(n) + g(n) ≥ g(n) ≥ 0

Adding both inequalities, f(n) + g(n) ≥ min(f(n), g(n))

⇒ min(f(n), g(n)) ≤ c.( f(n) + g(n)) for all n ≥ n_{0} with c = 1.

From the definition of big oh, min(f(n), g(n)) = O(f(n) + g(n)).

However converse is not true. Let us take f(n) = n and g(n) = n^{2}. i.e. min(f(n), g(n)) = n. It is easy to show that for any n_{0}, c there is always exist n such that n < c(n + n^{2}). So it is proved that min(f(n), g(n)) = Ω(f(n) + g(n)) is false.

Hence, the given statement is false.

**Example: **Prove that (n + a)^{b} = Θ( n^{b }), b > 0

To prove that said statement, we show find positive constants c_{1}, c_{2} and n_{0} such that 0 ≤ c_{1}n^{b} ≤ (n + a)^{b} ≤ c_{2}n^{b}, for all n ≥ n_{0}.

Here, a is constant, so for sufficient large value of n, n ≥ |a|, so

n + a ≤ n + | a |

This also implies, n + a ≤ n + |a| ≤ n + n

For further large value of n, n ≥ 2|a|, so |a| ≤ (n/2)

n + a ≥ n – |a| ≥ (n/2)

When n ≥ 2|a|, we have

0 = (1/2)n ≤ n + a ≤ 2n

Given that, b is positive constant, so raising the above equation to the power b does not change the relation,

0 = (n/2)^{b} ≤ (n + a)^{b} ≤ (2n)^{b}

0 = (1/2)^{b} (n)^{b } ≤ (n + a)^{b } ≤ (2)^{b }(n)^{b}

So the constants c_{1} = (1/2), c_{2} = 2 and n_{0} = 2|a| proves the given statement

**Example:** Is 2^{n+1} = Ο(2^{n}) ? Explain.

To prove the given statement, we must find constants c and n_{0} such that 0 ≤ 2^{n+1} ≤ c.2^{n} for all n ≥ n_{0}.

2^{n+1} = 2 * 2^{n} for all n. We can satisfy the given statement with c = 2 and n_{0} = 1.

**Example:** Find big theta and big omega notation of f(n) = 14 * 7 + 83

**1. Big omega notation :**

We have to find c and n_{0} such that 0 ≤ c **×** g(n) ≤ f(n) for all n ≥ n_{0}

0 ≤ c **×** g(n) ≤ f(n)

0 ≤ c **×** g(n) ≤ 14 * 7 + 23

0 ≤ c **×** g(n) ≤ 181 for all n ³ 1

0 ≤ 181.1 ≤ 181

For c = 181, g(n) = 1 and n_{0} = 1

f(n) = Ω(g(n)) = Ω(1) for c = 181, n_{0} = 1

**2. Big theta notation:**

We have to find such 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}

0 ≤ c_{1} .g(n) ≤ f(n) ≤ c_{2} **× **g(n)

0 ≤ c_{1 }**× **g(n) ≤ 181 ≤ c_{2} **× **g(n)

0 ≤ 180.1 ≤ 181 ≤ 182.1, for all n ³ 1

f(n) = Θ(g(n)) = Θ(1), for c_{1} = 180, c_{2} = 182, n_{0} = 1

Big oh notation is most commonly used in practice. In this course, we have analyzed many problems using big oh notation including various searching algoriths, sorting algoriths, reursive problems, etc.

**Additional Reading**: More Examples