Mumbai University > Information Technology > Sem 3 > Data Structure and Algorithm analysis

Marks: 3 M

Year: May 2015

1. Introduction:

i. Asymptotic analysis is used to evaluate the performance of an algorithm in terms of input size.

ii. The basic idea of asymptotic analysis is to measure the efficiency of algorithms that doesn’t depend on machine specific constants.

iii. The mathematical tools to represent time complexity of algorithms for asymptotic analysis are called as asymptotic notations.

2. Description:

i. There are 3 notations to measure time complexity of a program namely $Big-O, Big-Ω and Big-θ$.

ii. Big-O

• This notation defines an upper bound of an algorithm.
• The function f(n)=O(g(n)) if and only if fn<=c.g(n) for all n>=no where c and no are constants.
• Here, g(n) is known as upper bound on values of f(n).
• $E.g. f(n)=3n+3, g(n)=4n$.

iii. Big-Ω

• Ω notation provides an asymptotic lower bound.
• The function f(n)= Ω g(n) if f(n)>=c.g(n) for all n>=no where c and no are constants.
• Here, g(n) is known as lower bound on values of f(n).
• $E.g. f(n)= 3n+2 and g(n)=3n$.

iv. Big-θ

• The theta notation bounds a function from above and below, so it defines exact asymptotic behaviour. Hence, it is also known as tightly bound.
• The function f(n)= θ (g(n)) if c1.g(n) <= f(n) <= c2.g(n) for all n>=no where c1, c2 and no are constants.
• $E.g. f(n)=3n+2 , g(n)=n, C1=3 and C2=4$