Introduction to Asymptotic Notations.

Before implementing any algorithm as a program, we need to analyze which algorithm is good in terms of time and space.

Time: Which one can execute faster.

Memory: Which one can take less memory.

Here we are mainly going to focus on calculating the Time Complexity which generally depends on the size of the input. Let's understand this point with the help of an example.

Suppose we have an integer array and we want to add an element at the beginning of the list then to perform this operation we need one extra space at the end of the array and we have to shift all the elements of the array by one unit and the number of the shift we have made is equal to the number of elements present in the given array.

So from this small example, we can understand that Running Time mostly depends on the size of the input. Therefore, if the size of the input is n, then f(n) is a function of n that denotes the Time Complexity. Example:

From the above example, we conclude that most of the time is consumed by 12 but wait we cannot conclude just by checking for a single n value, we need to calculate a bigger value of n. Below is the calculation for bigger n values.

n	5n^2	6n	12
1	21.74%	26.09%	52.17%
10	87.41%	10.49%	2.09%
100	98.79%	1.19%	0.02%
1000	99.88%	0.12%	0.002%

Now if we observe the above table we found that for a bigger n value 5n^2 it takes most of the time so while calculating the Time Complexity we can neglect the remaining terms because the single term gives us the approximate result and it is very near to the actual result. This approximate measure of time complexity is called Asymptotic Complexity.

What are Asymptotic Notations?

Asymptotic notations are mathematical tools to measure the space and time complexity of an algorithm. There are mainly three asymptotic notations used to show the time complexity of the algorithm.

O(n) Big O notation. (Worst Case)

Big O notation is the most used notation to measure the performance of any algorithm by defining its order of growth.

Assuming that the time and input are going to increase like in the above graph then what is the worst-case or upper bound for this function?
We have to find out another function in such a way that the function is greater than the given f(n), let's call it c.g(n), after some limit n=no

For any given algorithm, we should be able to find out what is its time complexity or what its f(n) in terms of input n. Now after finding out that, if we can bound that function by some another function say c.g(n) in such a way that after some input no, the value of c.g(n) is always greater than f(n).

[ f(n)<=c.g(n) ], after some n where is n>=no

c, n are real numbers, c > 0 and n >=no

Definition: f(n) ∈ O(g(n)) if there exists constants c > 0 and no > =1 such that 0 <= f(n) <= c.g(n) for all n >= no

Example: Is f(n) is big O of g(n) [f(n) = O(g(n))] where f(n) = 3n+2 and g(n) = n.

Solution: At first we have to find two constants c and no such that,
f(n)<=c.g(n), c > 0 and n >=no

3n+2 < cn.

let's take c=4

3n+2 < 4n

=> n>=2

Therefore, f(n) = O(g(n)).

Therefore, g(n) = n bounds the function f(n) which means f(n) is upper bounded by g(n).

So if n is bounding this f(n) then definitely n^2 will bound. It means if g(n) = n is satisfying then any value greater than n (n^2, n^3,----n^n) will also bound 3n+2, but we need to keep in mind that big O is always the upper bound, so all the answers are correct but we will always go for least bound or tightest bound and n is the tightest bound for given f(n).

Ω(n) Omega notation. (Best Case)

Omega notation gives us a lower bound of the complexity in the best case analysis. In this notation, we analyze the minimum number of steps that need to be executed. For example, In Linear search, the best case is when your search element is present in the first place.

We have to find out another function in such a way that the function is smaller than the given f(n), let's call it c.g(n), after some limit n=no
Now after finding out that, if we can bound that function by some another function say c.g(n) in such a way that after some input no, the value of c.g(n) is always smaller than f(n).

[ f(n)>=c.g(n) ], after some n where is n>=no
c, n are real numbers, c > 0 and n >=no

Definition: f (n) ∈ Ω(g(n)) if there exists constants c > 0 and n0 >= 1 such that 0 ≤ c ·g(n) ≤ f (n) for all n ≥ n0

Example: Is f(n) is big Omega of g(n) where f(n) = 3n+2 and g(n) = n.

Solution:

3n+2 >= cn. is true even for c = 1

Therefore, the condition is satisfied and 3n+2 is lower bounded by n.

The given function f(n) can be lower bounded by any value lower than n but it's better to take the closest bound.

Θ(n) Theta notation. (Average Case)

Theta notation gives us a tight bound of the complexity in the average case analysis. In this notation, we calculate the average by considering different inputs, including the best and worst cases.

Here we have to find out both the upper bound and lower bound, by a function by a function by varying c.
If f(n) is bounded by c1g(n) and c2g(n) then, f(n) is Θg(n).

Definition: f (n) ∈ Θ(g(n)) if there exists constants c1 > 0, c2 > 0 and n0 > 1 such that c1 ·g(n) ≤ f (n) ≤ c2 ·g(n) for all n ≥ n0

Example: Is f(n) is big Theta of g(n) where f(n) = 3n+2 and g(n) = n.

Solution:

f(n) ≤ c2 ·g(n)

3n+2 ≤ 4n, true for n0 ≥ 1.

f(n) ≥ c1 ·g(n)

3n+2 ≥ n, true for n0 ≥ 1 and c = 1

This means, that f(n) = 3n+2 is bounded by g(n) from both upper as well as lower bound, for upper bound c2 = 4, and for lower bound c1 = 1, both the cases are valid for n0 ≥ 1.

Note: Sometimes, Θ is also called asymptotically equal which means if the leading term in the function is going to be 1, then we can take n as g(n) because they are asymptotically equal.

Ex: f(n) = 3n^2+n+1 = Θ(n^2).

f(n) = 5n^3+n+1 = Θ(n^3).

👉Support Us by Sharing our post with others if you really found this useful and also share your valuable feedback in the comment section below so we can work on them and provide you best 😊.(alert-success)