home
|
about
/
cs
/
cs341
/
master theorem
+2 more
Work in Progress
Summary
Master theorem
Concept
Master Theorem
generalizes the runtime of a class of
recurrence relations
T
(
n
)
n
c
w
ork
T
(
n=b
)
(
n=b
)
c
w
ork
¢
¢
¢
T
(
n=b
)
(
n=b
)
c
w
ork
T
(
n=b
2
)
(
n=b
2
)
c
w
ork
¢
¢
¢
T
(
n=b
2
)
(
n=b
2
)
c
w
ork
T
(
n=b
2
)
(
n=b
2
)
c
w
ork
¢
¢
¢
T
(
n=b
2
)
(
n=b
2
)
c
w
ork
.
.
.
.
.
.
.
.
.
.
.
.
T
(1)
T
(1)
¢
¢
¢
T
(1)
¢
¢
¢
T
(1)
T
(1)
lev
el
0
lev
el
1
lev
el
2
.
.
.
lev
el
log
b
n
1
no
de
a
no
des
a
2
no
des
.
.
.
a
log
b
n
=
n
log
b
a
lea
v
es
heigh
t
=
log
b
n
A
t
lev
el
k
:
a
k
no
des,
eac
h
with
w
ork
¡
n
b
k
¢
c
.
T
otal
w
ork
at
lev
el
k
:
a
k
¡
n
b
k
¢
c
=
n
c
¡
a
b
c
¢
k
.
Application