Asymptotic notations

In the previous post, I discussed about asymptotic bounding and why do we need to understand asymptotic analysis. There are few notations used to do the asymptotic analysis and I will be discussing the same in this post.

Prerequisites:

Basic understanding of asymptotic analysis is required. Refer Asymptotic bounding or asymptotic analysis.

Explanation:

Every piece of code or an algorithm requires certain amount of time and space. It is important to analyze the time and space required so that we can make our algorithm more efficient. Asymptotic bounding shows the nature of a function or an algorithm when tested with large values of ‘n’ i.e. large input size.

Asymptotic notations are used to do used to represent the work done by a function when tested with large input values.

Consider T(n) as the function with the input of size ‘n’.

Types of asymptotic notations:

Upper bound – Big O – O(n) – Worst case analysis

T(n) is O(f(n)) iff T(n) <= c * f(n) for all n>= n0.

The above can be read as “T(n) is upperbounded by f(n) if and only if T(n) is less than or equal to some constant c times f(n) for all values of n greater than equal to n0”.

Assume that T(n) = 3n+2 and f(n) = n, then according to the equation T(n) <= c * f(n) for all n>= n0, we get

3n+2 <= c*n, we need to choose a value of c such that 3n+2 <= c*n. If c is considered as 4 then the equation becomes 3n+2 <= 4n which means 2<= 4n-3n i.e 2<=n. Hence for n>=2 and c=4, T(n) <= c*f(n).

Hence, if T(n) = 3n+2 and f(n)=n then T(n) <= c*f(n) which is proved above. So, if f(n)=n is upper bounding T(n), then higher order functions like f(n)=n^2, f(n)=n^3 will also upper bound T(n). But the tightest bound is f(n)=n.

Lower bound – Big Omega – Ω(n) – Best case analysis

T(n) is Ω(f(n)) iff T(n) >= c*f(n) for all n>=n0.

The above can be read as “T(n) is lower bounded by f(n) if and only if T(n) is greater than or equal to some constant c times f(n) for all values of n greater than equal to n0”.

Assume that T(n) = 3n+2 and f(n) = n, then for T(n) = Ω(f(n))

3n+2 >= c*n, we need to choose a value of c such that 3n+2 >= c*n. If we consider c=1, then 3n+2 >= n which is true. Hence T(n) = Ω(f(n)) with n0>=1 and c=1.

If we consider f(n)=n^2, then 3n+2 >= c*n*n i.e 3n+2 >= c*n^2 which is not possible for any values of c. i.e. T(n) cannot be lower bounded by f(n) with f(n) = n^2 or any higher order of n.

Average bound – Big theta – Θ – Average case analysis

T(n) = Θ(f(n)) iff c1*f(n) <= T(n) <= c2*f(n) where c1,c2 are constants and c1,c2>0 and n>=n0 where n0>=1.

The above can be read is “T(n) is lower and upper bounded by f(n) if and only if c1*f(n) is less than or equal to T(n) which is less than or equal to c2*f(n)”.

We have already seen that T(n) <= c2*f(n) when T(n)=3n+2, f(n)=n and c2=4.

3n+2 <= 4*n, for all c2>=1 and n0>=1.

And T(n) >= c1*f(n) where T(n)=3n+2, f(n)=n and c1=1, hence 3n+2 >= n which is true.

Hence T(n) is upper as well as lower bounded by f(n).

Significance of asymptotic notations:

1. Big O notation ‘O’ which is also known as the upper bound represents the worst case analysis. It bounds the function only from above. It says that the time/space taken by an algorithm will not exceed the value represented by Big O notation.
2. Big Omega notation ‘Ω’ which is also known as lower bound represents the best case analysis. It bounds the function only from below.It says that the time/space taken by an algorithm will not be less than the value represented by Omega Ω notation.
3. Big theta Θ represents the average case analysis. It bounds the function from above as well as below.

Example:

Consider an array with size of 10 elements as below,

10

2

5

4

1

3

7

6

9

8

For example, we want to search an element in the array using linear search.

Linear search is a searching algorithm in which the element to search is compared with all the elements of array one by one.

Suppose if the element to be searched is 10. 10 is present at index 0 i.e. at the first position in the array, then it can be found in the least possible time using only 1 comparison. Hence this is the best case and can be represented by Omega notation Ω(1). If the element to be searched is 8, then we will need to compare 8 with all the elements of the array up to the last element i.e. it will require 10 comparisons which is the worst case scenario having maximum number of comparisons required. Hence this will be the worst case scenario and can be represented by Big O notation O(n), where n = size of the input array.

In the next post I will be discussing how to calculate the time complexity of a function and represent it using an asymptotic notation.Stay tuned.

I hope this post helped you to understand the asymptotic notations. Feel free to provide your feedback and comments in the comment box below. Thank you.