6.

Asymptotics
Asymptotic approximations
Goal: Develop accurate and concise estimates of quantities of interest

not accurate

not concise

(log )

ln + +(

)
Big-Oh notation for upper bounds
Little-oh notation for lower bounds
Tilde notation for asymptotic equivalence
Notation (revisited)
() = (()) |()/()| s bounded rom ubove us
() = (()) ()/()
() () ()/()
Approximations
() = () + (())
() = () + (())
() ()
Tilde approximation
Little-oh approximation
Big-Oh approximation
Weakest nontrivial o-approximation.
Error will decrease relative to h(N ) as N increases.
Error will be within a constant factor of h(N ) as N increases.
Standard asymptotic scale
Definition. A decreasing series gk(N) with gk+1(N) = o(gk(N )) is called an
asymptotic scale. The series
is called an asymptotic expansion of f. The expansion represents the collection
of formulae
Use ~-notation to drop information on unused terms.
Use O-notation or o-notation to specify information about unused terms.
Typically we use only 3 or 4 terms.
Unused terms are typically extremely small (by comparison with first few terms).
Methods extend in principle to any desired precision.
()

() +

() +

() + . . .
() = (

())
() =

() + (

())
() =

() +

() + (

())
() =

() +

() +

() + (

())

The standard scale is products of powers of N, log N, iterated logs and exponentials.
Theorem. Assume that a rational GF f (z)/g(z) with f (z) and g(z) relatively
prime and g(0)=0 has a unique pole 1/ of smallest modulus and that the
multiplicity of is . Then
Asymptotics of linear recurrences
[

]
()
()

=
()

(/)

()
(/)
Proof sketch

<

<

+. . . +

<

Largest term dominates.

Easy to extend to cover multiple poles of smallest modulus.
Example.
2
N
+ 1.99999
N
~ 2
N
Theorem. Assume that a rational GF f (z)/g(z) with f (z) and g(z) relatively
prime and g(0)=0 has a unique pole 1/ of smallest modulus and that the
multiplicity of is . Then
Asymptotics of linear recurrences
[

]
()
()

=
()

(/)

()
(/)
Example from earlier lectures.

= 5
l
6
2
or 2 vth
0
= 0 und
l
= l
Make recurrence valid for all n.

Solve.
() =

+

Multiply by z
n
and sum on n.
() = ()

() +
Smallest root of
denominator is 1/3.

=
()(/)
+ /
=
Fundamental asymptotic expansions
are immediate from Taylors theorem.
exponential
logarithmic
binomial
geometric

= + +

+ (

)
ln( + ) =

+ (

)
( + )

= + +

+ (

= + +

+ (

)
as x 0.
Fundamental asymptotic expansions
are immediate from Taylors theorem.
exponential
logarithmic
binomial
geometric
as N .

/
= +

+(

==

+(

)
ln( +

) =

+(

)
( +

= +

+(

)
Substitute x = 1/N to get expansions as N .
Inclass exercise
Develop asymptotic approximations
=

+(

+(

)
=

+(

)
=

+(

) +

+(

)
=

+(

)
ln( +

) + ln(

) (/

)
ln( +

) ln(

) (/

)
Goal.
Develop expansion on the standard scale for any given expression.
Manipulating asymptotic expansions

ln(+ )

Techniques.
simplification
substitution
factoring
multiplication
division
composition
exp/log

Why?
Facilitate comparisons of different quantities.
Simplification. An asymptotic series is only as good as its O-term.
Discard smaller terms.
Manipulating asymptotic expansions
ln + +()
ln +()

Substitution. Change variables in a known expansion.

ln( +

) =

+(

))
ln( + ) =

+ (

)
Taylor series
Substitute x = 1/N
Factoring. Estimate the leading term, factor it out, expand the rest.
Manipulating asymptotic expansions

+
Factor out 1/N
2
.
=

+/
Expand the rest.
Distribute.
=

+(

+(

Multiplication. Do term-by-term multiplication, simplify, collect terms.

Manipulating asymptotic expansions
Precision typically lost in the process (may need trial-and-error).
(

ln + +(

ln + +(

Term-by-term
multiplication.
=

(ln )

+ ln +(
log

ln +

+(

(
log

) +(

) +(

Collect terms. = (ln )

+ ln +

+(
log

)
Simplify.
= (ln )

+ ln + ln +

+(
log

)
Division. Expand, factor denominator, expand 1/(1x), multiply.
Manipulating asymptotic expansions

ln(+ )
Expand.
=
ln + +(

)
ln +(

)
Expand 1/(1x).
=

+

ln
+(

+(

Multiply.
= +

ln
+(

)
=
+

ln
+(

)
+(

)
Factor
denominator.
OK to simplify by replacing
O(1/N log N) by O(1/N)
Composition. Substitute an expansion.
Substitute HN
expansion.
=
ln + +(/)
Manipulating asymptotic expansions

(/)
Simplify.
=

( +(

Distribute.
=

+()
Lemma.

(/)
= +(

)
Expand e
x
. =

( +(

) +

Exp/log. Start by writing f (x) = exp(ln(f (x)).

Manipulating asymptotic expansions

Exp/log.
= exp

ln

= exp

ln

Expand ln(1+x) = exp

+(

Distribute.
= exp

+(

= +(

)
Lemma.

(/)
= +(

)
Inclass exercises
= ln + ln(

)
= ln

+(

)
Factor out ln N.
Expand the rest.
Develop asymptotic approximations
ln() (/

)
(

(/)
= (ln )

+ ln +

+
ln

+(

)
(

ln + +

+(

ln + +

+(

Bounding the tail. Make a rapidly decreasing sum infinite.

Asymptotics of nite sums
!

()

!
= !

= !

>
()

!
|

| <

+
+

(+ )

+

(+ )

+ . . . =

=
!

+(

)
Using the tail. The last term of a rapidly increasing sum may dominate.

! = !

!
!

= !

+(

N 1 terms, each less than 1/N(N 1)

Approximating with an integral.

= ln
ln ! =

ln

ln = ln +
see text for proofs;
stay tuned for
better approximations
Euler-Maclaurin Summation
is a classic formula for estimating sums with integrals.
Theorem. (Euler-Maclaurin summation). Let f be a function defined on
[1, ) whose derivatives exist and are absolutely integrable. Then

() =

() +

() +

()

() + . . .
Asymptotic series diverges; need to check bound on last term (see text for many details).
BUT this form is useful for many applications.
Examples.

= ln + +

+(

)
ln ! = ln + ln

+(

)
Inclass exercise
Given Stirlings approximation
Develop an asymptotic approximation for
= exp

ln ln

+(/)

+(

to (l/) (reutve error)

= exp

ln

!) ln !

ln ! = ln + ln

+(

)
= exp

ln() + ln

+(/)
(ln() + ln

+(/))

ln

ln

= ln ln

ln

= ln

Bivariate asymptotics
is often required to analyze functions of two variables.
Typical applications in analysis of algorithms involve
N (size)
k (cost)
Challenges:
asymptotics depends on relative values of variables
may need to approximate sums over whole range of relative values.
Ramanujan Q-distribution
Binomial distribution.
Examples:

!
()!

for k=0
exponentially small for k close to N
1 for k=0
exponentially small for k close to N
Approximation to the Ramanujan Q-distribution
!
()!

= exp

ln ! ln()! ln

ln ! = (+

) ln + ln

+(

)
= exp

( +

) ln + ln

( +

) ln() + ln

ln + (

= exp

( +

) ln(

) +(

ln(

) =

+(

)
= exp

+(

) +(

+ (

) + (

k k/N k
3
/N
2
N
2/5
1/N
3/5
1/N
4/5
N
1/2
1/N
1/2
1/N
1/2
N
3/5
1/N
2/5
1/N
1/5
Normal approximation to the binomial distribution
= exp

( +

) ln() + ln

+ (/)
( +

) ln() + ln

+ (/)
( + +

) ln( + ) ln

+ (/)

= exp

ln

!) ln()! ln( + )!

= exp

) ln ln

( +

)(ln(

) + ln( +

)) +(ln(

) ln( +

)) + (/)

= exp

() ln ln

+ (

) + (

= exp

() ln ln

( +

) ln(

) ( + +

) ln( +

) + (/)

ln ! = (+

) ln + ln

+(

+ (

) + (

ln(

) + ln( +

) =

+(

)
ln(

) ln( +

) =

+(

)
Fundamental bivariate approximations
uniform central
normal
Poisson
Q

!
()!

+ (

/
)

!
+ ()

/()
+ (

+ (

) + (

/()

+ (

) + (

+ (

) + (

Laplace method
To evaluate a sum:
Restrict the range to an area that contains the largest summands.
Approximate the summand.
Extend the range by bounding the tails to get a simpler sum.
Approximate the new sum with an integral.
Laplace method for Ramanujan Q-function
To evaluate
()

!
()!

Restrict the range to an area that contains the largest summands.

() =

!
()!

<
!
()!

Take k0 = o(N
2/3
).
Approximate the summand.

!
()!

/
Q-distribution
approximation.
Extend the range by bounding the tails to get a simpler sum.
()

/ Both tails are

exponentially small.
Approximate the new sum with an integral.
()

/
=

/
Assignments for next lecture
1. Exercise 4.70 Show that
2. Read pages 153-219 (Asymptotics) in text.
Prepare a question/discussion point on 1. or 2.
() =

()

()!
!
=

/ + ()