home
|
about
/
cs
/
cs341
/
recurrence relations
+2 more
Work in Progress
Concept
Proving merge sort
T
(
n
)
n
w
ork
T
(
n=
2)
n=
2
w
ork
T
(
n=
2)
n=
2
w
ork
T
(
n=
4)
n=
4
w
ork
T
(
n=
4)
n=
4
w
ork
T
(
n=
4)
n=
4
w
ork
T
(
n=
4)
n=
4
w
ork
.
.
.
.
.
.
.
.
.
.
.
.
T
(1)
T
(1)
¢
¢
¢
T
(1)
¢
¢
¢
T
(1)
T
(1)
lev
el
0
lev
el
1
lev
el
2
.
.
.
lev
el
log
2
n
1
no
de
2
no
des
2
2
=
4
no
des
.
.
.
2
log
2
n
=
n
lea
v
es
heigh
t
=
log
2
n
A
t
lev
el
k
:
2
k
no
des,
eac
h
with
w
ork
n
2
k
.
T
otal
w
ork
p
er
lev
el:
2
k
n
2
k
=
n
.
Therefore
T
(
n
)
=
£(
n
log
n
).
Application
Extra
Swapping base and power
using the
rules of logarithms