Java Reference
In-Depth Information
cubic. In others, the most efficient algorithm is even worse (exponential). Further-
more, when the amount of input is small, any algorithm will do. Frequently the
algorithms that are not asymptotically efficient are nonetheless easy to program.
For small inputs, that is the way to go. Finally, a good way to test a complex lin-
ear algorithm is to compare its output with an exhaustive search algorithm. In
Section 5.8 we discuss some other limitations of the Big-Oh model.
the logarithm
5.5
The list of typical growth rate functions includes several entries containing
the logarithm. A
logarithm
is the exponent that indicates the power to which a
number (the base) is raised to produce a given number. In this section we look
in more detail at the mathematics behind the logarithm. In Section 5.6 we
show its use in a simple algorithm.
We begin with the formal definition and then follow with more intuitive
viewpoints.
The
logarithm
of
N
(to the base 2) is
the value
X
such
that 2 raised to the
power of
X
equals
N
. By default, the
base of the loga-
rithm is 2.
definition:
For any
BN
,
>
0
log
N
=
K
if
B
K
=
N
.
B
In this definition,
B
is the base of the logarithm. In computer science, when
the base is omitted, it defaults to 2, which is natural for several reasons, as we
show later in the chapter. We will prove one mathematical theorem, Theorem 5.4,
to show that, as far as Big-Oh notation is concerned, the base is unimportant, and
also to show how relations that involve logarithms can be derived.
Theorem 5.4
The base does not matter. For any constant
B
>
1
,
log
N
=
O
(log
N
)
.
B
Let
log
N
=
K
. Then
B
K
=
N
. Let
C
=
log
B
. Then
2
C
=
B
. Thus
Proof
B
B
K
=
()
2
C
K
=
N
. Hence, we have
2
CK
=
N
, which implies that
log
N
=
KC N
B
=
log
. Therefore
log
N
=
(
log
N
)
⁄
(
log
B
)
, thus completing the
B
proof.
In the rest of the text, we use base 2 logarithms exclusively. An important fact
about the logarithm is that it grows slowly. Because 2
10
= 1,024, log 1,024 = 10.
Additional calculations show that the logarithm of 1,000,000 is roughly 20, and
the logarithm of 1,000,000,000 is only 30. Consequently, performance of an
algorithm is much closer to a linear algorithm than to a qua-
dratic algorithm for even moderately large amounts of input. Before we
look at a realistic algorithm whose running time includes the logarithm, let us
look at a few examples of how the logarithm comes into play.
O
(
N
log
N
)
O
(
N
)
ON
( )
Search WWH ::
Custom Search