Information Technology Reference
In-Depth Information
log
n
3
.
0
log(
n
+
1
)
2
.
5
2
.
0
1
.
5
1
.
0
0
.
5
n
1
2
3
4
5
6
7
8
9
10 11 12 13
Figure 2.23
The natural logarithm of the factorial
n
!
is
k
=
1
ln
k
,whichisboundedbelow
by
1
ln
xdx
and above by
1
ln(
x
+
1
)
dx
.
2.2 Derive tight upper and lower bounds on the factorial function
n
!=
n
(
n
−
1
)
···
321.
Hint:
Derive bounds on
ln
n
!
where
ln
is the natural logarithm. Use the information
giveninFig.
2.23
.
2.3 Let
T
(
d
)
be a complete balanced binary tree of depth
d
.
T
(
1
)
,showninFig.
2.24
(a),
has a root and two leaves.
T
(
d
)
is obtained by attaching to each of the leaves of
T
(
1
)
copies of
T
(
d
−
1
)
.
T
(
3
)
isshowninFig.
2.24
(b).
T
(
d
)
has 2
d
leaves and 2
d
−
a)
1 non-leaf vertices.
b) Show that any binary tree (each vertex except leaves has two descendants) with
n
leaves has
n
Show by induction that
−
log
2
n
1 non-leaf vertices and depth at least
.
(a) (b)
Figure 2.24
Complete balanced binary trees a) of depth one and b) depth 3.
Search WWH ::
Custom Search