Asymptotic Notation

In this article, I am going to discuss Asymptotic Notation. Please read our previous article where we discussed the Analysis of Algorithm and why it is important to analyze the algorithm. At the end of this article, you will understand the following pointers in detail with examples.

1. What are Asymptotic Notations?
2. Big-O Notation
3. Omega-Q Notation
4. Theta-Θ Notation
5. Why is it called Asymptotic Analysis?

Asymptotic Notation
Having the expressions for the best, average, and worst cases, for all three cases we need to identify the upper and lower bounds. To represent these upper and lower bounds, we need some kind of syntax, and that is the subject of the following discussion. Let us assume that the given algorithm is represented in the form of function f(n).

The following 3 asymptotic notations are mostly used to represent the time complexity of algorithms.

Big-O Notation [Upper Bounding Function]
This notation gives the tight upper bound of the given function. Generally, it is represented as f(n)= O(g(n)). That means, at larger values of n, the upper bound of f(n) is g(n). For example, if f(n)= n4 + 100n2 + 10n + 50 is the given algorithm, then n4 is g(n). That means g(n) gives the maximum rate of growth for f(n) at larger values of n.

O(g(n)) = { f(n): there exist positive constants c and n0 such that 0 <= f(n) <= c*g(n) for all n >= n0 }.
The statement f(n) = O(g(n)) states only that g(n) is an upper bound f(n) for all n , n >= n0 .
Note: In below Big- 0 Examples n0 denoted by n0.

Big-O Examples

Example-1 Find upper bound for f(n) = 3n + 8
Solution: 3n + 8 ≤ 4n, for all n ≥ 8
3n + 8 = O(n) with c = 4 and n0 = 8

Example-2 Find upper bound for f(n) = n2 + 1
Solution: n2 + 1 ≤ 2n2 , for all n ≥ 1
n2 + 1 = O(n2) with c = 2 and n0 = 1

Example-3 Find upper bound for f(n) = n4 + 100n2 + 50 Solution: n4 + 100n2 + 50 ≤ 2n4, for all n ≥ 11
n4 + 100n2 + 50 = O(n4) with c = 2 and n0 = 11

Example-4 Find upper bound for f(n) = 2n3 – 2n2
Solution: 2n3 – 2n2 ≤ 2n3, for all n > 1
2n3 – 2n2 = O(n3) with c = 2 and n0 = 1

Example-5 Find upper bound for f(n) = n
Solution: n ≤ n, for all n ≥ 1
n = O(n) with c = 1 and n0 = 1

Example-6 Find upper bound for f(n) = 410 Solution: 410 ≤ 410, for all n > 1
410 = O(1) with c = 1 and n0 = 1

No Uniqueness?
There is no unique set of values for n0 and c in proving the asymptotic bounds. Let us consider, 100n + 5 = O(n). For this function, there are multiple n0 and c values possible.

Solution1: 100n + 5 ≤ 100n + n = 101n ≤ 101n, for all n ≥ 5, n0 = 5 and c = 101 is a solution. Solution2: 100n + 5 ≤ 100n + 5n = 105n ≤ 105n, for all n > 1, n0 = 1 and c = 105 is also a solution.

Omega-Q Notation [Lower Bounding Function]
Similar to the O discussion, this notation gives the tighter lower bound of the given algorithm and we represent it as f(n) = Ω(g(n)). That means, at larger values of n, the tighter lower bound of f(n) is g(n). For example, if f(n) = 100n2 + 10n + 50, g(n) is Ω(n2).

For a given function g(n), we denote by Ω(g(n)) the set of functions. Ω (g(n)) = {f(n): there exist positive constants c and n0 such that 0 <= c*g(n) <= f(n) for all n >= n0}.

Omega (Ω) Examples
Example-1 Find lower bound for f(n) = 5n2.
Solution: ∃ c, n0 Such that: 0 ≤ cn2≤ 5n2 ⇒ cn2 ≤ 5n2 ⇒ c = 5 and n0 = 1 5n2 = Ω(n2) with c = 5 and n0 = 1

Example-2 Prove f(n) = 100n + 5 ≠ Ω(n2).
Solution: ∃ c, n0 Such that: 0 ≤ cn2 ≤ 100n + 5 => 100n + 5 ≤ 100n + 5n(∀n ≥ 1) = 105n => cn2 ≤ 105n ⇒ n(cn – 105) ≤ 0 Since n is positive ⇒cn – 105 ≤0 ⇒ n ≤105/c ⇒ Contradiction: n cannot be smaller than a constant

Theta-Θ Notation [Order Function]
The theta notation bound functions from above and below, so it defines exact asymptotic behavior. A simple way to get Theta notation of an expression is to drop low order terms and ignore leading constants. For example, consider the following expression.

3n3 + 6n2 + 6000 = Θ(n3)

Dropping lower order terms is always fine because there will always be a n0 after which Θ(n3) has higher values than Θn2) irrespective of the constants involved.

For a given function g(n), we denote Θ(g(n)) is following set of functions.

Θ(g(n)) = {f(n): there exist positive constants c1, c2 and n0 such that 0 <= c1*g(n) <= f(n) <= c2*g(n) for all n >= n0}

The above definition means, if f(n) is theta of g(n), then the value f(n) is always between c1*g(n) and c2*g(n) for large values of n (n >= n0). The definition of theta also requires that f(n) must be non-negative for values of n greater than n0.

Theta (Θ) Examples

Example 1 Prove n ≠ Θ(n2)
Solution: c1n2 ≤ n ≤ c2n2 ⇒ only holds for: n ≤ 1/c1
n ≠ Θ(n2)

Example 2 Prove 6n3 ≠ Θ(n2)
Solution: c1n2≤ 6n3 ≤ c2n2 ⇒ only holds for n ≤ c2/6
6n3 ≠ Θ(n2)

Example 3 Prove n ≠ Θ(logn)
Solution: c1logn ≤ n ≤ c2logn ⇒ c2 ≥ n/log n, ∀ n ≥ n0 – Impossible

Important Notes
For analysis (best case, worst case, and average), we try to give the upper bound (O) and lower bound (Ω) and average running time (Θ). From the above examples, it should also be clear that, for a given function (algorithm), getting the upper bound (O) and lower bound (Ω) and average running time (Θ) may not always be possible. For example, if we are discussing the best case of an algorithm, we try to give the upper bound (O) and lower bound (Ω) and average running time(Θ).

In the remaining chapters, we generally focus on the upper bound (O) because knowing the lower-bound (Ω) of an algorithm is of no practical importance, and we use the Θ notation if the upper bound (O) and lower bound (Ω) are the same.

Why is it called Asymptotic Analysis?
From the discussion above (for all three notations: worst case, best case, and average case), we can easily understand that in every case for a given function f(n) we are trying to find another function g(n) which approximates f(n) at higher values of n. That means g(n) is also a curve which approximates f(n) at higher values of n.

In mathematics, we call such a curve an asymptotic curve. In other terms, g(n) is the asymptotic curve for f(n). For this reason, we call algorithm analysis asymptotic analysis.

In the next article, I am going to discuss Properties of Asymptotic Notations. Here, in this article, I try to explain Asymptotic Notation. I hope you enjoy this Asymptotic Notation article. I would like to have your feedback. Please post your feedback, question, or comments about this article.

Summary:
I hope this post will be helpful to understand the concept of Asymptotic Notation
Please share this post with your friends and colleagues.
For any queries please post a comment below.
Happy Coding 😉