# 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 n0 such that 0 ≤ f(n) ≤ c.g(n) for all n ≥ n0. 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 n0 such that 0 ≤ f (n) ≤ c.g(n) for all n ≥ n0

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 n0= 1

f(n) = O(g(n)) = O(1) for c = 6993, n0 = 1

f(n) = O(g(n)) = O(1) for c = 8000, n0 = 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 n0 such that 0 ≤ f (n) ≤ c × g (n) for all n ≥ n0

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,  n0 = 1

Tabular Approach

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

0 ≤ 6n + 3 ≤ 7 n

Now, manually find out the proper n0, such that f (n) ≤ c.g (n)

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

f(n) = O(g(n)) = O(n) for c = 9, n0 = 1

f(n) = O(g(n)) = O(n) for c = 7, n0 = 3

and so on.

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

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

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

0 ≤ 3n2 + 2n + 4 ≤ c × g (n)

0 ≤ 3n2 + 2n + 4 ≤ 3n2 + 2n2 + 4n2

for all  n    ≥   1:

0 ≤ 3n2 + 2n + 4 ≤ 9n2

0 ≤ 3n2 +2n + 4 ≤ 9n2

So, c = 9, g(n) = n2  and  n0 = 1

Tabular approach:

0 ≤ 3n2 + 2n + 4 ≤ c.g (n)

0 ≤ 3n2 + 2n + 4 ≤ 4n2

Now, manually find out the proper n0, such that f(n) ≤ c.g(n)

From Table, for n ≥ 4, f(n) ≤ c × g (n) holds true. So, c = 4, g(n) = n2 and n0 = 4. There can be such multiple pair of (c, n0)

f(n) = O (g(n)) = O (n2)  for c = 9,  n0 = 1

f(n) = O (g(n)) = O (n2)  for c = 4, n0 = 4

and so on.

Example: Find upper bound of running time of a cubic function f(n) = 2n3 + 4n + 5.

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

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

0 ≤ 2n3 + 4n + 5 ≤ c × g(n)

0 ≤ 2n3 + 4n + 5 ≤ 2n3+ 4n3 + 5n3, for all n  ³ 1

0 ≤ 2n3 + 4n + 5 ≤ 11n2

So, c = 11, g(n) = n3 and n0  = 1

Tabular approach

0 ≤ 2n3 + 4n + 5 ≤ c × g(n)

0 ≤ 2n3 + 4n + 5 ≤ 3n3

Now, manually find out the proper n0, such that f(n) ≤ c × g(n)

From Table, for n ≥ 3, f(n) ≤ c × g(n) holds true. So, c = 3, g(n) = n3 and n0 = 3. There can be such multiple pair of (c, n0)

f(n) = O(g(n)) = O(n3) for c = 11, n0 = 1

f(n) = O(g(n)) = O(n3) for c =3, n0 = 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 n0 such that 0 ≤ c.g(n) ≤ f(n) for all n ≥ n0. 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 n0 such that { 0 ≤ c × g(n) ≤ f(n) for all n ≥ n0 }

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 n0 = 1

f(n) = Ω (g(n)) = Ω (1) for c = 23, n0 = 1

f(n) = Ω (g(n)) = Ω (1) for c = 12, n0 = 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 n0 such that 0 ≤ c.g(n) ≤ f(n) for all n ≥ n0

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

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

0 ≤ 6n ≤ 6n + 3 → true, for all n ≥ n0

0 ≤ 5n ≤ 6n + 3 → true, for all n ≥ n0

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

f(n) = Ω (g(n)) = Ω (n) for c = 6, n0 = 1

f(n) = Ω (g(n)) = Ω (n) for c = 5, n0 = 1

and so on.

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

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

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

0 ≤ c × g(n) ≤ 3n2 + 2n + 4

0 ≤ 3n2 ≤ 3n2 + 2n + 4, → true, for all n ≥ 1

0 ≤ n2 ≤ 3n2 + 2n + 4,   → true, for all n ≥ 1

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

So, f(n) = Ω (g(n)) = Ω (n2) for c = 3, n0 = 1

f(n) = Ω (g(n)) = Ω (n2) for c = 1, n0 = 1

and so on.

Example: Find lower bound of running time of quadratic function f(n) = 2n3 + 4n + 5.

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

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

0 ≤ c × g (n) ≤ 2n3 + 4n + 5

0 ≤ 2n3 ≤ 2n3 + 4n + 5 → true, for all n ≥ 1

0 ≤ n3 ≤ 2n3 + 4n + 5 → true, for all n ≥ 1

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

So,   f(n) = Ω (g(n)) = Ω (n3) for c = 2, n0 = 1

f(n) = Ω (g(n)) = Ω (n3) for c = 1, n0 = 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 c1, c2, and n0 such that 0 ≤ c1× g(n) ≤ f(n) ≤ c2× g(n) for all n ≥ n0. 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 c1, c2 and n0 such that, 0 ≤ c1× g(n) ≤ f(n)  ≤ c2 × g(n)  for all n ≥ n0

0 ≤ c1× g(n) ≤ 23 ≤ c2 × 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,   (c1, c2) = (22, 24) and g(n) = 1, for all n ≥ 1

(c1, c2) = (10, 50) and g(n) = 1, for all n ≥ 1

f(n) = Θ (g (n)) = Θ (1) for c1 = 22, c2 = 24, n0 = 1

f(n) = Θ (g (n)) = Θ (1) for c1 = 10, c2 = 50, n0 = 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 c1, c2 and n0 such that, 0 ≤ c1× g(n) ≤ f(n) ≤ c2 × g(n)  for all n ≥ n0

0 ≤ c1× g(n) ≤ 6n + 3 ≤ c2 × 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 c1 = 5, c2 = 9, n0 = 1

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

To find tight bound of f(n), we have to find c1, c2 and n0 such that, 0 ≤ c1 × g(n) ≤ f(n) ≤ c2 × g(n)  for all n ≥ n0

0 ≤ c1 × g(n) ≤ 3n2 + 2n + 4 ≤ c2 × g(n)

0 ≤ 3n2 ≤ 3n2 + 2n + 4 ≤ 9n2, for all n ≥ 1

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

f(n) = Θ(g(n)) = Θ(n2) for c1 = 3, c2 = 9, n0 = 1

Example: Find tight bound of running time of a cubic function f(n) = 2n3 + 4n + 5.

To find tight bound of f(n), we have to find c1, c2 and n0 such that, 0 ≤ c1 × g(n) ≤ f(n) ≤ c2 × g(n)  for all n ≥ n0

0 ≤ c1 × g(n) ≤ 2n3 + 4n + 5 ≤ c2 × g(n)

0 ≤ 2n≤ 2n3 + 4n + 5 ≤ 11n3, for all n ≥ 1

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

f(n) = Θ(g(n)) = Θ(n3) for c1 = 2, c2 = 11, n0 = 1

## General Problems

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

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

To prove above statement, we have to find c1, c2 and n0 such that, 0 ≤ c1× g(n) ≤  f(n) ≤ c2 g(n)  for all n ≥ n0

0 ≤ c1× g(n) ≤ 3n + 2 ≤ c2 × g(n)

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

So,    f(n) = Θ(g(n)) = Θ(n) for c1 = 2, c2 = 5 n0 = 1

(ii)   6*2n + n2 = Θ(2n)

To prove above statement, we have to find c1, c2 and n0 such that, 0 ≤ c1× g(n) ≤  f(n) ≤ c2 g(n)  for all n ≥ n0

0 ≤ c1× g(n) ≤ 6*2n + n2 ≤ c2 × g(n)

0 ≤ 6.2n ≤ 6*2n + n2 ≤ 7*2n, for all n ≥ 1

So, f(n) = Θ(g(n)) = Θ(2n) for c1 = 6, c2 = 7 n0 = 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 ≥ n0.

For all such n ≥ n0, 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 ≥ n0 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) = n2. i.e. min(f(n), g(n)) = n. It is easy to show that for any n0, c there is always exist n such that n < c(n + n2). 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 = Θ( nb ), b > 0

To prove that said statement, we show find positive constants c1, c2 and n0 such that 0 ≤ c1nb ≤ (n + a)b ≤ c2nb, for all n ≥ n0.

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 c1 = (1/2), c2 = 2 and n0 = 2|a| proves the given statement

Example: Is 2n+1 = Ο(2n) ? Explain.

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

2n+1 = 2 * 2n for all n. We can satisfy the given statement with c = 2 and n0 = 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 n0 such  that  0 ≤ c × g(n) ≤ f(n) for all n ≥ n0

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 n0 = 1

f(n) = Ω(g(n)) = Ω(1) for c = 181, n0 = 1

2. Big theta notation:

We have to find such c1, c2 and n0 such that,

0 ≤ c1  × g(n) ≤ f(n)  ≤ c2 × g(n)  for all n ≥ n0

0 ≤ c1 .g(n) ≤ f(n)  ≤ c2 × g(n)

0 ≤ c1 × g(n) ≤ 181 ≤ c2 × g(n)

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

f(n) = Θ(g(n)) = Θ(1), for c1 = 180, c2 = 182, n0 = 1 Additional Reading: More Examples