Dmitry Kalashnikov

You might remember that a logarithm of a number is the power to which its base must be raised to produce your number. OK, that was a mouthful. Its much easier to describe with math examples. English just doesn’t cut it for things like this.

Base 10 Logs:

log10(1000)=3

10 ^ 3 = 1,000

Base 2 (lg):

lg 32 = 5

2 ^ 5 = 32

Binary Tree Example:

The height of a binary tree is lg num_nodes

If a tree has 16 nodes:

• common sense: its height is 4 — that’s how many “rows” it has
  
• lg 16 = 4
• proof: 2 ^ 4 = 16

So, as you can see … as n grows rapidly, lg(n) is growing very slowly. Why is this important? Its important in computer science, were we are always concern with what happens to our program when the data it processes increases. What happens to its speed if input data is of enourmous size? Will the algorithm choke?

As n approaches infinity … what happens to it? A lot of algorithms in computer science have this logarithmic properity …

(I’ll update this after I post some sorting algos)