lg n
log n
ln n

What's the difference?

log_a x = b      means a^b = x

log_5 125 = 3    because 5^3 = 125

log_81 9 = 0.5   because 81^0.5 = 9

log_b (xy) = log_b x + log_b y

log_b (x/y) = log_b x - log_b y

log_b (x^n) = n log_b x.

log_b a = (log_x b) / (log_x a)

log x = log_10 x (common logarithm)

ln x = log_e x (natural logarithm, e = 2.718281828459...)

lg x = log_2 x

lg x = log_2 x = ln x / ln 2  = (1/ln 2) ln x = constant * ln x = Theta (ln x).

lg 4 = 2.  lg 8 = 3.  lg 16 = 4.  lg 32 = 5.  lg 64 = 6.
lg 1024 = 10.  lg 65536 = 16.  lg 4194304 = 22.

Logarithmic functions are what we call "slow-growing functions."  They grow.  They grow all the way to infinity.  Eventually.  This is why logarithmic algorithms are very fast.

What famous algorithm runs in Theta (lg n) time?  Answer:  Binary Search

If I were to double the size of my data immediately, that would add ONE extra search to my binary search.

A data set of 65536 takes 16 lookups.
A data set of 131072 takes 17 lookups.

lg* n = the smallest number of lgs that will get you to a number less than or equal to 1. lg*1000000000 = 5  (I had to hit the lg button 5 times to get a number less than or equal to 1.)

n^2   n^3   (3/2)^n   which is fastest which is slowest?


lim n->inf n^2/n^3 = lim n->inf  1/n = 0  n^2 is faster than n^3.

n^c  is always faster than k^n.  n^1000000 is faster than (1.0000000000001)^n  (c >=0.  k > 1).

lim n->inf n^c / k^n .

DIGRESSION.

INDUCTION.  (PMI)

Suppose x is a natural number (a nonnegative integer).

If a certain property is true for x = 0.
AND I can demonstrate that WHENEVER the property is true for x = n, it is also true for x = n+1

THEN

I can conclude that the property is always true for x being any natural number.

PROVE that the sum of the first n odd numbers is n^2.

Is it true for n=0?  The sum of the first 0 odd numbers is 0, so yeah.

Suppose we know that the sum of the first k odd numbers is k^2.
What is the sum of the first k+1 odd numbers?

First of all, the kth odd number is 2k-1.

1 + 3 + 5 + 7 + 9 +  ... + 2k-1  + 2(k+1)-1
k^2 + 2(k+1)-1
k^2 + 2k +2 -1 = k^2 + 2k + 1 = (k+1)^2.  Tada.

Therefore, it's always true, by induction.

Prove by induction that all crayons in a box of crayons are the same color.

Suppose there is 1 crayon in a box.  Of course, all crayons are the same color in that case.

Assume it's true for k crayons.  Is it true for k+1 crayons?  It must be.

Pull any crayon out of the box, the remaining k crayons must be the same color as each other.  Put that crayon back; pull out a different one.  And THOSE k crayons must be the same color as each other.  Therefore, all k+1 crayons are the same color as each other.  TADA.

This proof "works" because there is an assumed third crayon in the box that is being compared to both of the crayons being pulled out.  However, when k=2, there is no third crayon, and so the proof fails at that point.