Asymptotic Analysis-2
Topics
Asymptotic notation using Limits
Definitions of O, Ω,Ө, o,ω notations
Analysis of Summations
Asymptotic Analysis
Using Limits
Use of basic definition for determining the asymptotic behavior is often awkward. It
involves ad hoc approach or some kind of manipulation to prove algebraic relations.
Calculus provides an alternative method for the analysis. It depends on evaluating
the following limit.
f(n)
lim = c
n→∞ g(n)
where f(n) is a growth function for an algorithm and g(n) is a standard function
Depending upon the value c , the relation between f(n) and g(n) can be expressed in terms
of asymptotic notations. In most cases it is easier to use limits, compared to basic method, to
determine asymptotic behavior of growth functions.
It will be seen that the Calculus notation n→ ∞ is equivalent to the algebraic condition
for all n ≥ n0 . Either of these conditions implies large input
O-Notation Using Limit
Definition
If f(n) is running time of an algorithm and g(n) is some standard growth function such
that
f(n)
lim —— = c , where c is a positive constant such that 0 ≤ c < ∞
n → ∞ g(n)
then f(n) = O ( g(n) )
Note that infinity is excluded from the range of permissible values for the constant c
O-Notation
Examples
Example(1): 3n2 + 5n+ 20 = O(n2)
lim
n → ∞
3n2 + 5n + 20
n2
=3+ 5 / n +20 / n2
= 3+0+0 =3 ( positive constant)
Therefore, 3n2 + 5n+ 20 = O(n2)
Example(2): 10n2 + 25n+ 7 = O(n3)
lim
n → ∞
10n2 + 25n + 7
n3
=10 / n+ 25 / n2 + 7 / n3
=0+0+0 = 0
Therefore, 10n2 + 25n+ 7 = O(n3)
O-Notation
Examples
Example(3): lg n = O(n)
lim
n → ∞
lg n
n =
∞ / ∞ ( Need to apply the L’ Hopital Rule )
In order to compute differential of lg n we first convert binary logarithm to natural logarithm.
Converting lg n (binary log ) to ln( n) ( natural log) , by the using formula lg n = ln n / ln 2
lim lg n =
(ln n) (Converting to natural log)
n → ∞
n (ln 2) n
lim
n → ∞ 1
ln 2. n ( Differentiating numerator and denominator)
= 0 ( Evaluating limits)
Therefore, lg n = O(n)
O-Notation
Examples
Example(4): n2 = O(2n)
lim
n → ∞ n2 =∞ / ∞ ( Need to apply the L’ Hopital Rule )
2n
Since d ( 2n ) = ln 2 . 2n, ( Calculus rule for differentiating the exponential functions)
dn
lim 2n (Differentiating numerator and denominator )
