Proof master theorem

Proof master theorem in Analysis of Algorithms

1. 1
Proof of Master Theorem
•The proof for the exact powers, n=b
k
for k³1.
•Lemma 4.2
–for T(n) = Q(1) if n=1
– aT(n/b)+f(n) if n=b
k
for k³1
–where a ³ 1, b>1, f(n) be a nonnegative function,
–Then
–T(n) = Q(n
log
b
a
)+ a
j
f(n/b
j
)
•Proof:
–By iterating the recurrence
–By recursion tree (See figure 4.3)
å
j=0
logb
n-1

2. 2
Recursion tree for T(n)=aT(n/b)+f(n)

3. 3
Proof of Master Theorem (cont.)
•Lemma 4.3:
–Let a ³ 1, b>1, f(n) be a nonnegative function defined on
exact power of b, then
–g(n)= a
j
f(n/b
j
) can be bounded for exact power of b as:
1.If f(n)=O(n
log
b
a
-e) for some e>0, then g(n)= O(n
log
b
a
).
2.If f(n)= Q(n
log
b
a
), then g(n)= Q(n
log
b
a
lg n).
3.If f(n)= W(n
log
b
a
+e) for some e>0 and if af(n/b) £cf(n) for some
c<1 and all sufficiently large n ³b, then g(n)= Q(f(n)).
å
j=0
logb
n-1

4. 4
Proof of Lemma 4.3
•For case 1: f(n)=O(n
log
b
a
-e) implies f(n/b
j
)=O((n /b
j
)
log
b
a
-e), so
•g(n)= a
j
f(n/b
j
) =O( a
j
(n /b
j
)
log
b
a
-e )
• = O(n
log
b
a
-e a
j
/(b
log
b
a
-e)
j
) = O(n
log
b
a
-e a
j
/(a
j
(b
-e)
j
))
• = O(n
log
b
a
-e (b
e)
j
) = O(n
log
b
a
-e (((b
e )

log
b
n
-1)/(b
e
-1) )
• = O(n
log
b
a
-e (((b
logb
n
)
e -1)/(b
e
-1)))=O(n
log
b
a
n
-e (n
e -1)/(b
e
-1))
• = O(n
log
b
a
)
å
j=0
logb
n-1
å
j=0
logb
n-1
å
j=0
logb
n-1
å
j=0
logb
n-1
å
j=0
logb
n-1

5. 5
Proof of Lemma 4.3(cont.)
•For case 2: f(n)= Q(n
log
b
a
) implies f(n/b
j
)= Q((n /b
j
)
log
b
a
), so
•g(n)= a
j
f(n/b
j
) = Q( a
j
(n /b
j
)
log
b
a
)
• = Q(n
log
b
a
a
j
/(b
log
b
a
)
j
) = Q(n
log
b
a
1)
• = Q(n
log
b
a
log
b
n) = Q(n
log
b
a
lg n)
å
j=0
logb
n-1
å
j=0
logb
n-1
å
j=0
logb
n-1
å
j=0
logb
n-1

6. 6
Proof of Lemma 4.3(cont.)
•For case 3:
–Since g(n) contains f(n), g(n) = W(f(n))
–Since af(n/b) £cf(n), a
j
f(n/b
j
) £c
j
f(n) , why???
–g(n)= a
j
f(n/b
j
) £ c
j
f(n) £ f(n) c
j
–

=f(n)(1/(1-c)) =O(f(n))
–Thus, g(n)=Q(f(n))
å
j=0
logb
n-1
å
j=0
logb
n-1
å
j=0
¥

7. 7
Proof of Master Theorem (cont.)
•Lemma 4.4:
–for T(n) = Q(1) if n=1
– aT(n/b)+f(n) if n=b
k
for k³1
–where a ³ 1, b>1, f(n) be a nonnegative function,
1.If f(n)=O(n
log
b
a
-e) for some e>0, then T(n)= Q(n
log
b
a
).
2.If f(n)= Q(n
log
b
a
), then T(n)= Q(n
log
b
a
lg n).
3.If f(n)=W(n
log
b
a+e
) for some e>0, and if af(n/b) £cf(n) for
some c<1 and all sufficiently large n, then T(n)=
Q(f(n)).

8. 8
Proof of Lemma 4.4 (cont.)
•Combine Lemma 4.2 and 4.3,
–For case 1:
•T(n)= Q(n
log
b
a
)+O(n
log
b
a
)=Q(n
log
b
a
).
–For case 2:
•T(n)= Q(n
log
b
a
)+Q(n
log
b
a
lg n)=Q(n
log
b
a
lg n).
–For case 3:
•T(n)= Q(n
log
b
a
)+Q(f(n))=Q(f(n)) because f(n)= W(n
log
b
a+e
).

9. 9
Floors and Ceilings
•T(n)=aT(ën/bû)+f(n) and T(n)=aT(én/bù)+f(n)
•Want to prove both equal to T(n)=aT(n/b)+f(n)
•Two results:
–Master theorem applied to all integers n.
–Floors and ceilings do not change the result.
•(Note: we proved this by domain transformation too).
•Since ën/bû£n/b, and én/bù³ n/b, upper bound for
floors and lower bound for ceiling is held.
•So prove upper bound for ceilings (similar for lower
bound for floors).

10. 10
Upper bound of proof for T(n)=aT(én/bù)+f(n)
•consider sequence n, én/bù, é én/bù/bù, é é én/bù /bù/bù,
…
•Let us define n
j
as follows:
•n
j
= n if j=0
• = én
j-1
/bù if j>0
•The sequence will be n
0
, n
1
, …, n
ëlog
b
nû

•Draw recursion tree:

11. 11
Recursion tree of T(n)=aT(én/bù)+f(n)

12. 12
The proof of upper bound for ceiling
–T(n) = Q(n
log
b
a
)+ a
j
f(n
j
)
–Thus similar to Lemma 4.3 and 4.4, the upper
bound is proven.
å
j=0
ëlogb
nû
-1

13. 13
The simple format of master theorem
•T(n)=aT(n/b)+cn
k
, with a, b, c, k are positive
constants, and a³1 and b³2,
O(n
logba
), if a>b
k
.
•T(n) = O(n
k
logn), if a=b
k
.
O(n
k
), if a<b
k
.