CS 244 Data Structures and Algorithms
Fall 1998 Moravian College
Tom Linton, http://www.cs.moravian.edu/~linton/

NAMES:

While the natural logarithm, , is by far the most convenient logarithm for calculus, in computer science the base 2 logarithm, , is nearly always used. This is due to the binary nature of computers and the frequency with which problems are solved by "dividing them in half", and solving the 2 smaller pieces. All logarithms (meaning for any > 1) are multiples of one another, so if you understand one logarithm function, you know them all. Take a look at a plot of several quotients of different logarithmic functions. NOTE: in Maple, both and represent the natural log.

> plot([ln(n)/log[2](n), log[5](n)/log[10](n),
log[8](n)/log[2](n)],
n=1..10,y=0..1.5, title="log ratios",
color=[red,black,blue]);

>

The fact that all those ratios are constant means the logarithms are multiples. For example, the red line is a plot of and because the graph is a horizontal line y = c (where c is close to 0.7), we see that

, or .

The value of c, in this case is ln(2).

> ln(2.);

Recall that , means that (a log is asking "what power of b gives n "). This explains why all logs are just multiples of one another. Say . That's the same as saying that . Now, if we take the natural log of both sides of this equation we get . Using a property of logs, namely that , we arrive at

or .

Finally, we started out by saying that , so we now have . NOTE: you can compute logs to other bases on your calculator with this, since a similar derivation will show that

,

and nearly all calculators today have a natural log key. For example, .

>

Logs arise frequently in the analysis of the run time of algorithms. Repeatedly dividing (integer division is best here) n by a fixed number b is related to . Let's go with n = 107 and b = 5. Just keep dividing by 5 until the result is zero, and count the number of divisions.

> div:=proc(n::integer, b::posint)
local val, count, ans;
val:=n:
count:=0:
ans:=[val]:
while val > 0 do
val:= floor(val/b);
ans:=[op(ans),val];
count:=count+1;
od;
print(divides = ans, num_divides = count);
end:

> div(107,5);

> log[5](107.);

> div(534,3);

> log[3](534.);

> div(12345678,2);

> log[2](12345678.);

>

Take n = your student ID number, and select b = 2, 3, 6, or 8. Repeatedly (integer) divide n by b until the result is zero. How many divisions did you perform?

Now, what is ?


Make up a statement (about and dividing repeatedly) that summarizes what you're seeing above.

Return to CS 244 materials page.