Java Reference
In-Depth Information
The first two properties state that the logarithm of two numbers multiplied (or
divided) can be found by adding (or subtracting) the logarithms of the two num-
bers. 4 Property (3) is simply an extension of property (1). Property (4) tells us that,
for variable n and any two integer constants a and b, log a n and log b n differ by
the constant factor log b a, regardless of the value of n. Most runtime analyses in
this topic are of a type that ignores constant factors in costs. Property (4) says that
such analyses need not be concerned with the base of the logarithm, because this
can change the total cost only by a constant factor. Note that 2 logn = n.
When discussing logarithms, exponents often lead to confusion. Property (3)
tells us that log n 2 = 2 log n. How do we indicate the square of the logarithm
(as opposed to the logarithm of n 2 )? This could be written as (log n) 2 , but it is
traditional to use log 2 n. On the other hand, we might want to take the logarithm of
the logarithm of n. This is written log log n.
A special notation is used in the rare case when we need to know how many
times we must take the log of a number before we reach a value 1. This quantity
is written log n. For example, log 1024 = 4 because log 1024 = 10, log 10
3:33, log 3:33 1:74, and log 1:74 < 1, which is a total of 4 log operations.
2.4
Summations and Recurrences
Most programs contain loop constructs. When analyzing running time costs for
programs with loops, we need to add up the costs for each time the loop is executed.
This is an example of a summation. Summations are simply the sum of costs for
some function applied to a range of parameter values. Summations are typically
written with the following “Sigma” notation:
n X
f(i):
i=1
This notation indicates that we are summing the value of f(i) over some range of
(integer) values. The parameter to the expression and its initial value are indicated
below the P symbol. Here, the notation i = 1 indicates that the parameter is i and
that it begins with the value 1. At the top of the P symbol is the expression n. This
indicates the maximum value for the parameter i. Thus, this notation means to sum
the values of f(i) as i ranges across the integers from 1 through n. This can also be
4 These properties are the idea behind the slide rule. Adding two numbers can be viewed as joining
two lengths together and measuring their combined length. Multiplication is not so easily done.
However, if the numbers are first converted to the lengths of their logarithms, then those lengths can
be added and the inverse logarithm of the resulting length gives the answer for the multiplication (this
is simply logarithm property (1)). A slide rule measures the length of the logarithm for the numbers,
lets you slide bars representing these lengths to add up the total length, and finally converts this total
length to the correct numeric answer by taking the inverse of the logarithm for the result.
Search WWH ::




Custom Search