Asymptotic Notation for Algorithm Analysis

Asymptotic Notation Overview

• O-, Q-, and O- notation
• Recursion tree
• Master method

O-notation (Upper Bounds)

We write
f(n) = O(g(n))
if there exist constants c>0, no >0 such that
Os f(n) ≤cg(n)
for all n > no
EXAMPLE: 2n2 = O(n3)
(c = 1, n = 2)
functions,
not values
funny, "one-way"
equality

Set Definition of O-notation

O(g(n)) = { f(n) : there exist constants c>0, n0 >0
such that
0 ≤ f(n) ≤ cg(n)
for all n> no}
Convention: A set in a formula represents
an anonymous function in the set.
EXAMPLE:
n2 + O(n) = O(n2)
means
for any f(n) = O(n):
n2 + f(n) = h(n)
for some h(n) € O(n2) .

Q-notation (Lower Bounds)

O-notation is an upper-bound notation. It makes
no sense to say f(n) is at least O(n2).
Q(g(n)) = {f(n) : there exist constants c>0, no >0
such that
0 ≤ cg(n) ≤ f(n)
for all n> no}
EXAMPLE:
Vn =Q(Ign) (c=1, n =16)

O-notation (Tight Bounds)

O(g(n)) = O(g(n)) n Q(g(n))
(g(n)) = {f (n) : there exist positive constants c1, C2, and n
such that
Os c,g(n) ≤ f(n) ≤ C2g(n)
for all n ≥ n0
EXAMPLE:
n2 -2n =(n2)

o-notation and w-notation

O-notation and Q-notation are like ≤ and 2.
o-notation and w-notation are like < and >.
o(g(n)) = {f(n) : for any constant c > 0, no >0
such that 0 < f(n) < cg(n) for all n> no}
EXAMPLE:
2n2 = o(n3)
(no =2/c)

w-notation Definition

w(g(n)) = {f(n) : for any constant c > 0, no >0
such that 0 _ cg(n) < f(n) for all n> no}
EXAMPLE:
Vn = w(1gn)
(n 0 = 1+1/c)

Solving Recurrences

• The analysis of merge sort required us to solve a
  recurrence.
• Recurrences are like solving integrals, differential
  equations, etc. Need to learn a few techniques.
• Applications of recurrences to divide-and-conquer
  algorithms.

Recursion-Tree Method

• A recursion tree models the costs (time) of a
  recursive execution of an algorithm.
• The recursion-tree method can be unreliable, just
  like any method that uses ellipses ( ... in a sentence).
• The recursion-tree method promotes intuition,
  however.
• The recursion tree method is good for generating
  guesses for the substitution method.

Example of Recursion Tree

Solve T(n) = T(n/4) + T(n/2) + n2:
n2
n2
5
n2
(n/4)2
(n/2)2
16
25
(n/16)2
/
(n/8)2
(n/8)2
(n/4)2
256
…
…
®(1)
Total = n2 (1+5+(5)
16
2
16
+1
3
5
16
n2
)
+ ...
= ®(n2)
geometric series

The Master Method

The master method applies to recurrences of the form
T(n) = a T(n/b) +f(n),
where a > 1, b > 1, and f is asymptotically positive.
Three typical cases

Comparing f(n) with nlogba

1. f(n) = O(nlogba -8) for some constant & > 0.
   
   • f(n) grows polynomially slower than nlogba
     (by an n& factor).
     Solution: T(n) = (nlogba).
2. f(n) = (nlogba 1gkn) for some constant k ≥ 0.
   T(n)=2 T(n/2)+ n Lg(n)
   a=2, b=2
   Log_b(a)=lg(2)=1
   
   • f(n) and nlogbª grow at similar rates.
     Solution: T(n) = (nlogba lgk+In) .
     is f(n) = Theta(n lg^k(n)) ?
     f(n) = n lg(n)
3. f(n) = Q(nlogba +&) for some constant > > 0.
   yes with k=1
   
   • f(n) grows polynomially faster than nlogba (by
     an nº factor),
     and f(n) satisfies the regularity condition that
     af(n/b) ≤cf(n) for some constant c < 1.
     Solution: T(n) = (f(n)) .

Master Method Examples

Ex. T(n) = 4T(n/2) +n
a = 4, b = 2 => nlogba = n2; f(n) = n.
CASE 1: f(n) = O(n2-&) for & = 1.
:. T(n) = O(n2).
Ex. T(n) = 4T(n/2) + n2
a = 4, b = 2 => nlogbª = n2; f(n) = n2.
CASE 2: f(n) = (n21gon), that is, k = 0.
.. T(n) = O(n21gn).
Ex. T(n) = 4T(n/2) + n3
a = 4, b = 2 => nlogba = n2; f(n) = n3.
CASE 3: f(n) = Q(n2 +8) for & = 1
and 4(n/2)3 < cn3 (reg. cond.) for c = 1/2.
:. T(n) = O(n3).:
n
n
ε
.
Ex. T(n) = 4T(n/2) + n2/1gn
a = 4, b = 2 => nlogbª = n2; f(n) = n2/1gn.
Master method does not apply. In particular,
for every constant & > 0, we have n& = @(lgn).

Idea of Master Theorem

T(n) = a T(n/b) +f(n),
Recursion tree:
f(n)
a
f(n/b) f(n/b)
. . .
f(n/b)
a
f(n/b2) f(n/b2) · f(n/b2)
I
…
1
T(1)

Recursion Tree Visualization

Recursion tree:
f(n
f(n/b) f(n/b) ...
a
f(n)
a
f(n/b)
af(n/b)
h = login
f(n/b2) f(n/b2) · f(n/b2)
I
…
#leaves = ah
… …
T(1)
= glogin
= plogba
logga T(1)
a'
h
login
In n
In a Inn
= a
= ainb = alna lnb =
= glosa n logs a = (gloga n) logs a = plogg a
reminder: log} (x) =
ln(x)
ln(b)
n
a2f(n/b2)

Recursion Tree Case 3

Recursion tree:
f(n
f(n)
a
f(n/b) f(n/b) ...
a
…
f(n/b)
af(n/b)
a
a
f(n/b2) f(n/b2) ... f(n/b2)
az f(n/b2)
…
…
…
T(1)
CASE 3: The weight decreases
geometrically from the root to the
leaves. The root holds a constant
fraction of the total weight.
…
…
…
…
…
"nlogbª T(1)
®(f(n))
h = login
…

Recursion Tree Summary

Recursion tree:
f(n)
f(n)
a
f(n/b) f(n/b) ...
.
a
…
a
h = login
f(n/b2) f(n/b2) · f(n/b2)
1
…
…
…
…
…
T(1)
pogba T(1)
=
f(n/b)
af(n/b)
a2f(n/b2)
…
…
…
logy n
T(n) =>af(n/b2) + O(n1086 a)
i=0

Three Cases of Master Theorem

1. If f(n) = O(nlosba-€) for some constant & > 0, then T(n) = O(nlosba).
2. If f (n) = (nlosba), then T(n) = O(n 0gb ª logn).
3. If f(n) = (nossa+€) for some constant > > 0, and if f satisfies the
   smoothness condition af (n/b) ≤ cf(n) for some constant c < 1, then
   T(n) = ℮(f(n)).
   X

Proof of Case (1)

Proof of case (1):
If f(n) = O(nlogba-) for some constant > > 0, then T(n) = O(n1086 a)
Given that we want to prove that T(n) is upper bounded by some quantity,
we may take advantage of inequalities.
log n
a f (n/b) + O(n10gb ª)
We know from the analysis of the tree that T(n) =
i=0
X
Thus, for case (1) we may write:
login
T(n) =>af(n/b) + (noBba) <
i=0
log৳ n
i=0
E ai (n/b2)logba-€
+ O(n10gb a)
because for this case we have
f(n) = (nogba-E)
,
i.e. for some & > 0
For n sufficiently large and for some constant c we have
i
X
X
X
=
=
f(n/b2) < c (n/b2)logga-E
)
X
a
1

Substitution in Sum

Thus by substitution in the sum we find (we don't need to write the constant in front)
"
logy n
X
i=0
a2 (n/b2)logga-E =n
logga-ε
=
logt n
X
a
i=0
logt n
X
i=0
nº6ª - 1
be - 1
-i logy azie
b
a^-i
= nlog
=
=
logga-ε
n^eps b^eps
logg n
Lala ibie
i=0
=n
logga-ε
=
=
This results, together with T(n)
i=0
a` f (n/b2)}+ O(n10gbª)
T(n) = O(nlogba)
i
=
X
⧠
a
Little Remark: O(f(n))+O(f(n)) is still O(f(n))
i
i
i
i
a
be
=n
logga-ε
<
n
logg a - E
nº be
be - 1
= n
= O(n ogb a)
1
logt n
logb a
be - 1
=
1
gives
X
)
=
=
bei =
logga-£
be(log} n +1) _ 1
be - 1
1
i

Proofs of Cases 2 and 3

Proofs of case-2 and case-3 are similar. I leave them to
you if you are interested (not required for the exam).