Scribd
Upload
133 views

Asymptotic Notations

Uploaded by

sayan.pal.23
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
133 views

Asymptotic Notations

Uploaded by

sayan.pal.23
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 4

Design and Analysis of Algorithm

Topperworld.in

Asymptotic notation

Asymptotic Notations
• Asymptotic notations are the mathematical notations used to describe
the running time of an algorithm when the input tends towards a
particular value or a limiting value.
• For example: In bubble sort, when the input array is already sorted, the
time taken by the algorithm is linear i.e. the best case.
• But, when the input array is in reverse condition, the algorithm takes
the maximum time (quadratic) to sort the elements i.e. the worst case.
• When the input array is neither sorted nor in reverse order, then it
takes average time. These durations are denoted using asymptotic
notations.
There are mainly three asymptotic notations:
➢ Big-O notation
➢ Omega notation
➢ Theta notation
Big-O Notation (O-notation)
✓ Big-O notation represents the upper bound of the running time of an
algorithm.
✓ Thus, it gives the worst-case complexity of an algorithm.

©Topperworld
Design and Analysis of Algorithm

Example:
Consider the following f(n) and g(n)...
f(n) = 3n + 2
g(n) = n
If we want to represent f(n) as O(g(n)) then it must satisfy f(n) <= C g(n) for
all values of C > 0 and n0>= 1
f(n) <= C g(n)
⇒3n + 2 <= C n
Above condition is always TRUE for all values of C = 4 and n >= 2.
By using Big - Oh notation we can represent the time complexity as
follows... 3n + 2 = O(n).

Omega Notation (Ω-notation)


Omega notation represents the lower bound of the running time of an
algorithm.
Thus, it provides the best case complexity of an algorithm.

©Topperworld
Design and Analysis of Algorithm

Example:
Consider the following f(n) and g(n)...
f(n) = 3n + 2
g(n) = n
If we want to represent f(n) as Ω(g(n)) then it must satisfy f(n) >= C g(n) for
all values of C > 0 and n0>= 1
f(n) >= C g(n)
⇒3n + 2 >= C n
Above condition is always TRUE for all values of C = 1 and n >= 1.
By using Big - Omega notation we can represent the time complexity as
follows...
3n + 2 = Ω(n)

Theta Notation (Θ-notation)


Theta notation encloses the function from above and below.
Since it represents the upper and the lower bound of the running time of an
algorithm, it is used for analyzing the average-case complexity of an
algorithm.

©Topperworld
Design and Analysis of Algorithm

Consider the following f(n) and g(n)...


f(n) = 3n + 2
g(n) = n
If we want to represent f(n) as Θ(g(n)) then it must satisfy C1 g(n) <= f(n) <=
C2 g(n) for all values of C1 > 0, C2 > 0 and n0>= 1
C1 g(n) <= f(n) <= C2 g(n)
⇒C1 n <= 3n + 2 <= C2 n
Above condition is always TRUE for all values of C1 = 1, C2 = 4 and n >= 2.
By using Big - Theta notation we can represent the time compexity as
follows...
3n + 2 = Θ(n)

©Topperworld

You might also like