Asymptotic Notations

Asymptotic Notations
Asymptotic notations are mathematical tools to represent the
time complexities of the algorithms.

There are three different notations-

Big Omega (Ώ) – lower bound
Big Theta (θ) – tight bound
Big Oh (O) – upper bound
Asymptotic Notations
From the algorithm analysis, we found that the time complexity of the
algorithm would be any of the follows-
1< log n < √n < n < n log n < n2 < n3 < … < 2n < 3n < … < nn
Suppose we have a function given as
f(n) =2n2 + 3n+2
The highest degree in above function is n2, So all the time complexities
after n2 including itself will be the upper bound, all before including n2
itself will be the lower bound of the function. The n2 itself will be the tight
bound. tight bound

1< log n < √n < n < n log n < n2 < n3 < … < 2n < 3n < … < nn
lower bound upper bound

Hence, f(n)= O(n2), f(n)= O(n3), f(n)= O(2n) // upper bound

Similarly,

f(n)= Ώ(n2), f(n)= Ώ(n), f(n)= Ώ(logn) = Ώ(1)

For any function if f(n)= Ώ(n2) and f(n)= O(n2) then

f(n)= θ(n2). [known as tight bound]
Asymptotic Notations: Big O notation
Formal Definition:

f(n)= O(g(n)) if there exist positive

constant c and n0 such that-

f(n)<= c*g(n) for all values of n>= n0

Big-O gives the upper bound of a function

Asymptotic Notations: Big O notation
Formal Definition:
f(n)= O(g(n)) if there exist positive constant c and n0 such that-
f(n)<= c*g(n) for all values of n>= n0

If f(n) = 2n2+ 3n+1

If we make all statements n2 then statement will be 2n2+ 3n2 + n2
=6n2
and 2n2+ 3n+1 <= 6n2 for all values of n i.e., n>=1
f(n)<= c* g(n) and g(n) = 6n2, then it can be said that
f(n)<= 6 n2
So, we can say, f(n) <= O(g(n)) for c=6 and n0 =1
f(n)= O(n2)
Asymptotic Notations: Big O notation
f(n)= O(g(n)) if there exist positive constant c and n0 such that-
f(n)<= c*g(n) for all values of n>= n0

If f(n) = 2n2+ 3n+1

If we make all statements 2n then statement will be 2*2n + 3*2n + 2n
=6*2n
and 2n2+ 3n+1 <= 6*2n for all values of n0
f(n)<=c*g(n) and g(n) = 6*2n then it can be said that
f(n)<= 6 *2n
So, we can say, f(n) <= O(g(n)) for c=6 and n0 >=0
f(n)= O(2n)
Always write the closest function. For the above function, the closest
function is g(n)= 6n2
 Asymptotic Notations: Ώ notation
Formal Definition:
The lower bound of f(n) will be
Ώ(g(n)), i.e., f(n) = Ώ(g(n)), if there
exist positive constant c and n0
such that-

f(n)>= c*g(n) for all values of n>= n0

Omega gives the lower bound of a function

Asymptotic Notations: Ώ notation
Formal Definition:
f(n)= Ώ(g(n)) if there exist positive constant c and n0 such that-
f(n)>= c*g(n) for all values of n>= n0

If f(n) = 2n2+ 3n+1

If we discard everything except n2 then g(n)= n2 and f(n) = 2n2+
3n+1. So,
2n2+ 3n+1 >= 1* n2 for all values of n>= n0
f(n) >= c* g(n)

So, we can say, f(n) >= Ώ(g(n)) for c=1 and n0 >=1
= Ώ(n2)
Asymptotic Notations: θ notation
Formal Definition:
f(n)= θ(g(n)) if there exist positive
constant c1, c2, and n0 such that-
c1*g(n) <=f(n)<= c2*g(n) for all
values of n>= n0

Theta gives the tight bound of a function

Asymptotic Notations: θ notation
Formal Definition:
f(n)= θ(g(n)) if there exist positive constant c1, c2, and n0 such that-
c1*g(n) <=f(n)<= c2*g(n) for all values of n>= n0

If f(n) = 2n2+ 3n+1, then

1 * n2 <= 2n2+ 3n+1 <= 6 * n2
C1 * g(n) <= f(n) <= c2 * g(n)

Therefore, we can say f(n)= θ(g(n)) = θ(n2)

This is the tight bound and only one statement will be satisfied for
the tight bound. For the above we cannot say f(n)= θ(n) but for other
asymptotic notation there may be other condition which may also
satisfy.
Asymptotic Notations: Example
f(n)= n2 log n + n
Replace n by n2 log n for upper bound, discard everything after first
statement for lower bound.

n2 log n <= n2 log n + n <= 2*n2 log n

Lower bound Tight bound Upper bound

Same term for both lower and upper, so, we can get
the tight bound.

So, f(n) = O(n2 log n), f(n) = Ώ(n2 log n), f(n) = θ(n2 log n)
Asymptotic Notations

Find asymptotic upper bound for the f(n) = n!.

Asymptotic Notations
Find asymptotic upper bound for the f(n) = n!.
As, n!= n*(n-1)*(n-2)*(n-3)* … *2*1
To find the upper bound replace all statement by n
g(n) = n*n*n*n* … *n*n= nn
As per the asymptotic upper bound f(n) <=c*g(n), so
n! <= 1*nn for n>=1
Thus, we can say, f(n)= O(nn)

To find the lower bound replace all statement either by 1 or log n

g(n) = 1*1*1*1* … *1*= 1n or g(n) = log n* log n … * log n *= nlog n
As per the asymptotic lower bound f(n) >=c*g(n), so
f(n) = n! >= 1*1n for n>=n0 Thus, we can say, f(n)= Ώ(1)
f(n) = n!>= nlog n for n>=n0 Thus, we can say, f(n)= Ώ(nlog n)
Asymptotic Notations: Example
For average or tight bound, we can write,
1n <= n! <= nn

It can be observed that there is no common asymptotic values for

lower and upper bounds. Therefore, no tight bound will exists for
n!.
For many functions, tight bound do not exist. In such case upper
and lower bound can be used to represent the asymptotic bounds.

f(n) = O(nn)
f(n) = Ώ (1)
Asymptotic Notations: Example
f(n)= log n!
We can write as-
log(1*1*1*…*1) <= log (1*2*3…*n) <= log (n*n*n….*n*n)
1<= log n! <= log nn
1<= log n! <= nlog n
This also has no common terms for lower and upper bounds, so for
this also no tight bounds exists. In such cases upper bounds are used
for asymptotic bounds.
Please note, tight bound does not exist for the factorial functions.

Theta notations always tells the best value/ complexity while others
may not give closest value/ complexity. This means Big O and Big
Omega is used when we cannot find the exact figure/ complexity.
Properties of Asymptotic Notations
1. If f(n) is O(g(n)) then a* f(n) is also O(g(n)).
for e.g., f(n) = 2n2 +3 = O(n2) then
5*f(n)= 5*(2n2 +3)= 10n2 +15 => O(n2)
The same property also satisfy for Ώ (n) and θ(n).

2. If f(n) is given then f(n) = O(f(n).

for e.g., f(n) = 2n2 +3 = O(f(n)) = O(n2)
The same property also satisfy for Ώ (n) and θ(n).

3. If f(n) is O(g(n)) and g(n) is O(h(n)), then f(n) = O(h(n))

for e.g., f(n) = n, g(n) = n2 and h(n) = n3
n= O(n2) and n2 = O(n3), then
n= O(n3)
The same property also satisfy for Ώ (n) and θ(n).
Properties of Asymptotic Notations
4. Symmetric property
If f(n) is θ(g(n)) then g(n) is θ(f(n)).
for e.g., f(n) = 2n2 +3 = θ(n2)
g(n)= n2 +2 => θ(n2)
As both functions are same, they will be symmetric.
This property only satisfy for θ(n).

5. Transpose Symmetric
If f(n) is O(g(n)) then g(n) is Ώ (f(n)).
for e.g., f(n) = n +3 = O(n),
g(n) =2n2 +1 =O(n2)
Then, n= O(n2) and n2 = Ώ(n)
This property satisfy for big O and big omega.
Properties of Asymptotic Notations
6. If f(n) = O(g(n)) then f(n) =Ώ(g(n)), i.e.,
g(n) <= f(n) <= g(n), then
f(n)=θ(g(n))
Find the asymptotic bound for the following
i. If f(n)= O (g(n)), and d(n) =O(e(n)), then f(n)+ d(n)=?
Assume f(n)= n and d(n)= n2 then
f(n)+ d(n)= n+ n2 = O(n2)
If we take f(n)= n2 and d(n)= n then
f(n)+ d(n)= n2+ n = O(n2) = O(max(O(g(n), e(n)))
This means the asymptotic bound will be equal to the function having
greater bound.

ii. If f(n)= O (g(n)), and d(n) =O(e(n)), then f(n)* d(n)=?

Comparison of two Functions
Which of the following is greater? Method 1
n2 or n3 n n2 n3
1 1 1
Method 2 2 4 8
Take log for n2 and n3
3 9 27
Log n2 = 2Log n Log n3 = 3Log n 4 16 64

It can be observed from the above

It can be observed from the above
that n3> n2.
that 2Log n < 3Log n. So, n3> n2.

Important log formulas

a^logcb = b^logca ab = n then b= logan

log a/b= log a- log b log ab= log a + log b
logab = blog a
 Comparison of two Functions
Which of the following is greater? Which of the following is
f(n) = n2 log n or g(n) =n(log n)10 greater?√n √nlog n
f(n) = 3n or g(n) = 2 2

Apply log both sides

Important log formulas
log (n2 log n ) log [n(log n)10]
1. a^logcb = b^logca
log n2+ log log n log n + log (log n) 10
2. ab = n then b= logan
2log n+ log log n log n + 10 log log n
3. log a/b= log a- log b

Bigger Smaller 4. log ab= log a + log b

Term Term
b
Here, 2log n> log n so, n2 log n > n(log n)10 5. loga = b loga
 Comparison of two Functions
Which of the following is greater?
f(n) = nlog n or g(n) = 2√n

Which of the following is greater?

f(n) = 2n or g(n) = 22n

Which of the following is greater?

f(n) = 2n or g(n) =3n
 Comparison of two Functions
Which of the following is greater? Which of the following is greater?
f(n) = nlog n or g(n) = 2√n f(n) = 2n or g(n) = 22n
Apply log
log nlog n log 2√n Apply log
log n x log n √n log22 log 2n log 22n
log 2 n √n nlog22 2n log22
Apply log one more time n 2n
2 log log n ½ log n So, f(n) < g(n)

So, f(n) < g(n) Which of the following is greater?

f(n) = 2n or g(n) =3n
Both are asymptotically equal because we
are not changing function by applying log
 Comparison of two Functions
Which of the following is greater?
f1(n) = n3 n<100 f1(n) = f2(n)= n2
n2 n>=100

f2(n) = n2 n<10000 <100 >=10000

n3 n>=10000 f1(n) > f2(n) f2(n) > f1(n)

It can be observed from the analysis that f2(n) will always greater than
f1(n) for n>=10000.
Best, Worst, and Average case Analysis
Let's take an example of linear search
A= 7 10 12 9 21 15 6 8
If we want to search a key =21, 5 comparison will be needed
For any key such as 75, it is not present in the list so search will be unsuccessful.
As we are only interested in successful search so, check all possible cases for
successful search.
Case 1: if the key is the first element (7) of the list [Best case]
Best case time = 1 (constant)=> B(n)=1
Case 2: if the key is the last element (8) of the list [Worst Case]
Worst case time = n => w(n)=n
Case 3: Average case time= all possible case time/no. of cases
It is difficult to find the average case time for any algorithm and generally, it is
equivalent to worst case time.
= 1+2+3+… + n / n => [n(n+1)/2]/n= (n+1)/2
A(n) = (n+1)/2
Best, Worst, and Average case Analysis
Analyzing Asymptotic notations
Best case time
B(n)=1
B(n)=O(1)
B(n) = Ώ(1)
So, B(n) = θ(1)
Worst case time
w(n)=n
B(n)=O(n)
B(n) = Ώ(n)
So, B(n) = θ(n)

There is no fixed notation to represent best case or worst-case time. This can be
represented by any of the asymptotic notations. It is not true that best case can
always be represented by θ and worst case by O.