Java Reference
In-Depth Information
Proof of
Theorem 7.5
Following the second proof of Theorem 7.4, we assume that
N
is a power of
B
and let
N
=
B
M
. Then
N
/
B
=
B
M
- 1
and
N
k
= (
B
M
)
k
= (
B
k
)
M
. We assume that
T
(1) = 1
and
ignore the constant factor in
O
(
N
k
)
. Then we have the basic equation
M
TB
M
AT B
M
1
-
B
k
(
)
=
(
)
+
()
If we divide through by
A
M
, we obtain the new basic equation
-
TB
M
(
)
TB
M
1
(
)
B
k
-----
M
⎝
⎛⎞
---------------
=
---------------------
+
A
M
A
M
1
-
Now we can write this equation for all
M
, obtaining
TB
M
TB
M
1
-
B
k
-----
M
(
)
(
)
⎝
⎛⎞
---------------
=
---------------------
+
A
M
A
M
1
-
TB
M
1
-
TB
M
2
-
B
k
-----
M
1
-
(
)
(
)
⎝
⎛⎞
=
+
---------------------
---------------------
A
M
1
-
A
M
2
-
(7.9)
TB
M
2
-
TB
M
3
-
B
k
-----
M
2
-
(
)
(
)
⎝
⎛⎞
=
+
---------------------
---------------------
A
M
2
-
A
M
3
-
…
1
TB
1
TB
0
B
k
-----
()
A
1
()
A
0
⎝
⎛⎞
=
+
--------------
--------------
If we add the collective denoted by Equation 7.9, once again virtually all the terms on
the left-hand side cancel the leading terms on the right-hand side, yielding
T
B
M
B
k
-----
i
(
)
⎝
⎛⎞
M
=
1
+
∑
---------------
i
=
1
A
M
B
k
-----
i
M
⎝
⎛⎞
=
∑
i
=
0
Thus
B
k
-----
i
M
⎝
⎛⎞
T
()
TB
M
A
M
∑
(7.10)
=
(
)
=
i
=
0
If
A
>
B
k
, then the sum is a geometric series with a ratio smaller than
1
. Because the
sum of an infinite series would converge to a constant, this finite sum is also
bounded by a constant. Thus we obtain
(continued on next page)
Search WWH ::
Custom Search