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

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

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

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

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

Tabular Approach

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

0 ≤ 6n + 3 ≤ 7 n

Now, manually find out the proper n₀, 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₀ = 3, There can be such multiple pair of (c, n₀)

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

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

and so on.

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

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

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

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

0 ≤ 3n² + 2n + 4 ≤ 3n² + 2n² + 4n², 

for all  n    ≥   1:

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

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

So, c = 9, g(n) = n²  and  n₀ = 1

Tabular approach:

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

0 ≤ 3n² + 2n + 4 ≤ 4n²

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

n	f(n) = 3n2 + 2n + 4	c.g (n) = 4n2
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² and n₀ = 4. There can be such multiple pair of (c, n₀)

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

f(n) = O (g(n)) = O (n²)  for c = 4, n₀ = 4

and so on.

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

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

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

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

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

0 ≤ 2n³ + 4n + 5 ≤ 11n²

So, c = 11, g(n) = n³ and n₀  = 1

Tabular approach

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

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

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

n	f(n) = 2n3 + 4n + 5	c.g(n) = 3n3
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³ and n₀ = 3. There can be such multiple pair of (c, n₀)

f(n) = O(g(n)) = O(n³) for c = 11, n₀ = 1

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

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

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

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

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

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

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

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

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

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

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

and so on.

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

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

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

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

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

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

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

So, f(n) = Ω (g(n)) = Ω (n²) for c = 3, n₀ = 1

f(n) = Ω (g(n)) = Ω (n²) for c = 1, n₀ = 1

and so on.

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

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

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

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

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

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

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

So,   f(n) = Ω (g(n)) = Ω (n³) for c = 2, n₀ = 1

f(n) = Ω (g(n)) = Ω (n³) for c = 1, n₀ = 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₁, c_2, and n₀ such that 0 ≤ c₁× g(n) ≤ f(n) ≤ c₂× g(n) for all n ≥ n₀. 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₁, c₂ and n₀ such that, 0 ≤ c₁× g(n) ≤ f(n)  ≤ c₂ × g(n)  for all n ≥ n₀

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

(c₁, c₂) = (10, 50) and g(n) = 1, for all n ≥ 1

f(n) = Θ (g (n)) = Θ (1) for c₁ = 22, c₂ = 24, n₀ = 1

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

0 ≤ c₁× g(n) ≤ 6n + 3 ≤ c₂ × 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₁ = 5, c₂ = 9, n₀ = 1

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

To find tight bound of f(n), we have to find c₁, c₂ and n₀ such that, 0 ≤ c₁ × g(n) ≤ f(n) ≤ c₂ × g(n)  for all n ≥ n₀

0 ≤ c₁ × g(n) ≤ 3n² + 2n + 4 ≤ c₂ × g(n)

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

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

f(n) = Θ(g(n)) = Θ(n²) for c₁ = 3, c₂ = 9, n₀ = 1

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

 To find tight bound of f(n), we have to find c₁, c₂ and n₀ such that, 0 ≤ c₁ × g(n) ≤ f(n) ≤ c₂ × g(n)  for all n ≥ n₀

0 ≤ c₁ × g(n) ≤ 2n³ + 4n + 5 ≤ c₂ × g(n)

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

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

f(n) = Θ(g(n)) = Θ(n³) for c₁ = 2, c₂ = 11, n₀ = 1

General Problems

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

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

To prove above statement, we have to find c₁, c₂ and n₀ such that, 0 ≤ c₁× g(n) ≤  f(n) ≤ c₂ g(n)  for all n ≥ n₀

0 ≤ c₁× g(n) ≤ 3n + 2 ≤ c₂ × g(n)

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

So,    f(n) = Θ(g(n)) = Θ(n) for c₁ = 2, c₂ = 5 n₀ = 1

(ii)   6*2ⁿ + n² = Θ(2ⁿ)

To prove above statement, we have to find c₁, c₂ and n₀ such that, 0 ≤ c₁× g(n) ≤  f(n) ≤ c₂ g(n)  for all n ≥ n₀

0 ≤ c₁× g(n) ≤ 6*2ⁿ + n² ≤ c₂ × g(n)

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

So, f(n) = Θ(g(n)) = Θ(2ⁿ) for c₁ = 6, c₂ = 7 n₀ = 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₀.

For all such n ≥ n₀, 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₀ 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². i.e. min(f(n), g(n)) = n. It is easy to show that for any n₀, c there is always exist n such that n < c(n + n²). 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₁, c₂ and n₀ such that 0 ≤ c₁n^b ≤ (n + a)^b ≤ c₂n^b, for all n ≥ n₀.

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/2), c₂ = 2 and n₀ = 2|a| proves the given statement

Example: Is 2ⁿ⁺¹ = Ο(2ⁿ) ? Explain. 

To prove the given statement, we must find constants c and n₀ such that 0 ≤ 2ⁿ⁺¹ ≤ c.2ⁿ for all n ≥ n₀.

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

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

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

2. Big theta notation:

We have to find such c₁, c₂ and n₀ such that,

0 ≤ c₁  × g(n) ≤ f(n)  ≤ c₂ × g(n)  for all n ≥ n₀

0 ≤ c₁ .g(n) ≤ f(n)  ≤ c₂ × g(n)

0 ≤ c₁ × g(n) ≤ 181 ≤ c₂ × g(n)

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

f(n) = Θ(g(n)) = Θ(1), for c₁ = 180, c₂ = 182, n₀ = 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