Learning Logarithms

Definition of Logarithms
Logarithms are simply a means of defining the value of a number by using the exponent of another number.
For example, 2 raised to the 10th power is 1024. Therefore we say that log base 2 of 1024 is equal to 10. We might express this as follows: log₂(1024) = 10.

In the example above the number 2 is considered to be the base of the logarithm and 10 is the exponent (or the log itself). Here the word log is simply short for logarithm.

Similarly log₁₀(1000) = 3 since 10³ = 1000.

Logarithms were invented so that very large numbers could be expressed and manipulated without requiring as many symbols. For example, 1,000,000,000 is simply 9 when written as a logarithm in base 10.

There are three bases that are typically used for logarithms.

base 10 (referred to as the common logarithm)

base e (referred to as the natural logarithm is usually written as ln)

base 2 (used primarily in Computer Science)

e is a special number that often naturally arises in many scientific disciplines. Although it is an infinite, non-repeating decimal, it aproximately equals 2.718281828. One special propery of e is the derivative of the function e^x is itself.

Base 2 is favored in Computer Science for several reasons. One of which is that computers store numbers in base 2. Another reason is that many computer algorithms tend to repeatedly divide a component of a problem in half.

Based upon the discussion above we see that we may define logarithms as follows:
Definition 1.1:
log_b(x) = n if and only if bⁿ = x

Rules of Logarithms with their proofs
For each of the following rules and proofs that are written using the natural log (ln), there is an identical or very similar result for bases other than e.

1.2
ln(a*b) = ln(a) + ln(b)
Proof:
ln(a*b) = ln(e^ln(a)*e^ln(b)) by the definition of logarithm (1.1).

= ln(e^{(ln(a)+ln(b))}) by the law of exponents.

= ln(a)+ln(b) by the definition of logarithm (1.1). 1.3
ln(a/b) = ln(a) - ln(b)
Proof:
ln(a/b) = ln(e^ln(a)/e^ln(b)) by the definition of logarithm (1.1).

= ln(e^{(ln(a)-ln(b))}) by the law of exponents.

= ln(a)-ln(b) by the definition of logarithm (1.1). 1.4
ln(aⁿ) = n*ln(a)
Proof:
Use mathematical induction on 1.2

1.5
log_b(a) = 1/log_a(b)
Proof:
Let log_b(a) = x
Then b^x = a
by definition of logarithm.
b = a^1/x by raising each side to the 1/x power.
log_a(b) = 1/x by taking the log to the base a of each side.
x = 1/log_a(b) by inverting both sides
log_b(a) = 1/log_a(b) by substituting back for x.

1.6
log_b(a) = log_c(a)/log_c(b)
Proof omitted.

An Order of Complexity proof using logarithms

	Here is a proof that log2(N!) is THETA(N*log2(N)).
    You must supply a reason for each numbered step in the proof.

    1. N^N > N!
	therefore  log2(N^N) > log2(N!)
	therefore  log2(N^N) is OMEGA(log2(N!))

    2. log2(N^N) = N*log2(N)

    3. log2(N!) = log2(N) + log2(N-1) + ... + log2(2)

    4. log2(N!) > log2(N) + log2(N-1) + ... + log2(N/2)

    5. log2(N!) > (N/2)*log2(N/2)

    therefore     log2(N!)          (N/2)*log2(N/2)
             lim  ---------  >=  lim --------------
	          N*log2(N)         N*log2(N)

           (N/2)*log2(N/2)             N*log2(N) - N
    6. lim ---------------  =  .5*lim ----------------- = .5
           N*log2(N)                   N*log2(N)

                  log2(N!)
    therefore lim --------- >= .5
                  N*log2(N)

    therefore log2(N!) is OMEGA(N*log2(N))

    therefore log2(N!) is THETA(N*log2(N))