ALGORITHMS AND DATA STRUCTURES

Prof. Massimo Poncino

Lez 4 - Analysis of recursive programs: recurrences I

Analysis of
Algorithms recursive programs:
recurrences
II

Outline

Master method
Î The Master Method

Î Examples of complexity
analysis of recursive
algorithms

Master method Master method

Systematic method for Three cases depending
recurrences of the type on the outcome of the
c if n≤d comparison between
T(n) = f(n) and nlogba
aT(n / b) + f(n) if n>d

Where Case 1: f(n) < nlogbba

a≥1, b>1 are constant Case 2: f(n) ≈ nlogbba
f(n) is an asymptotically
positive function Case 3: f(n) > nlogbba

Copyright © Università Telematica Internazionale UNINETTUNO

1
 ALGORITHMS AND DATA STRUCTURES
Prof. Massimo Poncino
Lez 4 - Analysis of recursive programs: recurrences I

Master method: interpretation Master method: interpretation

Compare f(n) against nlog
log a
a b
b
Compare f(n) against nlog
log a
a b
b

Case 1 Case 3
f(n) = Ω (nlog
logbb a
a++εε
) → T(n) = Θ(f(n))
log
logbb a
a--εε
f(n) = O (n ) for some ε > 0
and if a ⋅ f(n / b) ≤ δ ⋅ f(n) for some δ < 1

f(n) < nlog

logbb a
a
T(n) = Θ(nlog
logbb a
a
) f(n) > n
log
logbb a
a
⇒ T(n) = Θ(f(n))

Master method: interpretation Master method

Compare f(n) against n log
logbb a
a Putting all cases together
log
logbb a
a−−εε log
logbb a
a
Case 2 f(n) = O (n ) → T(n) = Θ(n )

f(n) = Θ (nlog
logbb a
a
) log
logbb a
a log
logbb a
a
f(n) = Θ (n ) → T(n) = Θ(n log n)

f(n) ≈ n
log
logbb a
a
⇒ T(n) = Θ(f(n) ⋅ log n) f(n) = Ω (nlog
logbb a
a++εε
) → T(n) = Θ(f(n))
for some ε > 0
and if a ⋅ f(n / b) ≤ δ ⋅ f(n) for some δ < 1

Master method: interpretation Master method: comments

The theorem does not
The relations between cover all cases for f(n)
f(n) and nlog
log a
a b
b

must hold polynomially Between cases 1 and 2 there are

intervals in which f(n) < nlog
log a
a b
b

but not polynomially

Must compare f(n) and Between cases 2 and 3 there are
log a++εε and
log a log
log a
a−−εε
n b
b
n b
b
intervals in which f(n) > nlog
log a
a b
b

but not polynomially

Copyright © Università Telematica Internazionale UNINETTUNO

2
 ALGORITHMS AND DATA STRUCTURES
Prof. Massimo Poncino
Lez 4 - Analysis of recursive programs: recurrences I

Master method: examples Master method:

generalized version
T(n) = 2T(n/2) + nlogn
log
logbb a
a−−εε log
logbb a
a
f(n) = O (n ) → T(n) = Θ(n )
a=2, b=2

logbba = log222 = 1 → nlogba

logba = n
f(n) = Θ (nlog
logbba
a
logkk n) → T(n) = Θ(nlog
logbba
a
logkk++11 n)

a++εε
But cannot compare f(n) = Ω (nlog
logbb a
) → T(n) = Θ(f(n))
polynomially nlogn and n ! for some ε > 0
and if a ⋅ f(n / b) ≤ δ ⋅ f(n) for some δ < 1

Master method: examples Informal proof of

master method
T(n) = 2T(n/2) + nlogn Structure of recursion tree
a=2, b=2 At each level
a sub-problems of size n/b
logbba = log222 = 1 → nlogba
logba = n

Height of tree = logbn

Now, we fall in Case 2,
with k=1 → f(n) = nlogbba · log1n

T(n) = Θ(n log22 n)

Structure of recursion tree Informal proof of

master method
Number of leaves
# of nodes at level i: ai f(n/bi)
At the last level i=logbn

alog
logbb n
n
⋅ f(1) = alog
logbb n
n
⋅ Θ(1) = nlog
logbb a
a

log
logbb n
n−−1
1
Total Θ(nlog
logbb a
a
)+ ∑ a f(n/b )
jj==0
jj jj

Copyright © Università Telematica Internazionale UNINETTUNO

3
 ALGORITHMS AND DATA STRUCTURES
Prof. Massimo Poncino
Lez 4 - Analysis of recursive programs: recurrences I

Informal proof of Master method: examples

master method
log
logbb n
n−−1
1 T(n) = T(n / 2) + c
Θ(nlog
logbb a
a
)+ ∑ a f(n/b )
jj==0
jj jj

0
a=1 b=2

log
logbb a
a
Cost of Cost of divide logb a = log2 1 = 0 ⇒ n =1
b 2

the leaves and combination

f(n) = Θ(1) = Θ(nlog
logbb a
a
) Case 2
(k=0)
Master theorem compares
these two quantities T(n) = log2 n
2

Master method: examples Master method: examples

T(n)=3T(n/4)+nlogn
T(n)=9T(n/3)+n
f(n) = n log n
log
logbb a log
log33 9
a=9 b=3 n
a
=n
9
= n22 a=3 b=4 n
log
logbb a
a log
log44 3
=n
3
= n00,,79
79

f(n) = n f(n) = O(nlog

logbb a
a++εε
) = Ω(n11)

Case 3 if f is regular,
f(n) = Ο(n
log
logbb a
a−−1
1
) = Ο(n11) Case 1 that is, a·f(n/b) ≤ δ f(n)
3·n/4·log(n/4) ≤ δ·n·log n if δ=3/4
T(n) = Θ(n22) T(n) = Θ(n lg n)

Example: mergesort

mergeSort(S
mergeSort(S,
,l,r)
l,r)
mergeSort(S,l,r)
Example of if (l<r)
complexity analysis m = ⎣ (l+r)/2⎦
(l+r)/2⎦
of recursive (S,l,m);
mergeSort(S,l,m
mergeSort );
mergeSort(S,l,m);
algorithms mergeSort(S,m+1,r);
mergeSort(S,m+1,r);
merge(S,l,m,r);
merge(S,l,m,r);
endif

Copyright © Università Telematica Internazionale UNINETTUNO

4
 ALGORITHMS AND DATA STRUCTURES
Prof. Massimo Poncino
Lez 4 - Analysis of recursive programs: recurrences I

Example: mergesort Example: factorial

Recurrence
T(n) = 2T(n/2) + O(n) Factorial(n)
{
2 recursive Cost of if n = 1
calls on “divide” and
return 1
two halves merge()
else
a=2, b=2 → nlogbba = n return (n ∗ Factorial(n-1))
}
f(n)=n
Case 2 T(n)=O(nlogn)

Example: factorial Example: factorial

Recurrence Θ(1) Θ(1)

Θ(1) Θ(1)
⎧ Θ(1) for n ≤ 1
T(n) = ⎨
⎩ T(n − 1) + Θ(1) for n > 1
… Θ(1) Θ(1)
n
Cannot use master theorem
Solve by iteration building
Θ(1) Θ(1)
the recursion tree
T(n) = n·Θ(1) = Θ(n)

Example: recursive minimum Example: recursive minimum

RecMinimum(A,l,r) Recurrence
if r-l ≤ 1 ⎧Θ(1) for n ≤ 2
T(n) = ⎨
then return (min(A[l], A[r])) ⎩2T(n / 2) + Θ(1) for n > 2
else
Use master theorem
mid = ⎣(l+r)/2⎦
m1 = RecMinimum(A,l,mid) a=2, b=2 ⇒ nlogbba = nlog222 = n
m2 = RecMinimum(A,mid+1,r)
T(n) = Θ(n)
return (min(m1, m2))

Copyright © Università Telematica Internazionale UNINETTUNO

5
 ALGORITHMS AND DATA STRUCTURES
Prof. Massimo Poncino
Lez 4 - Analysis of recursive programs: recurrences I

Algorithms

Copyright © Università Telematica Internazionale UNINETTUNO