COT 3400 - Logs & Exponents

Vocabulary flashcards covering definitions and key rules about logarithms and exponentials.

Logarithm

log_b(a) = c if b^c = a. The exponent to which base b must be raised to yield a.

Exponent–Log Inverse Rule 1

b^log_b(n) = n. Raising base b to the logarithm of n with base b recovers n.

Exponent–Log Inverse Rule 2

log_b(b^k) = k. Logarithm of a base-b power returns the exponent k.

Common Mistake: b * log_b(n) ≠ n

Multiplying log by the base is not equivalent to n; the correct inverse is exponential: b^log_b(n) = n.

Change of Base Formula

log_b(n) = log_k(n) / log_k(b). Used to convert a logarithm from an original base b to a new desired base k. For the formula to be valid, all variables (n, b, k) must be positive, and both bases (b and k) cannot be equal to 1.

Exponent Law: Product

b^x * b^y = b^(x+y).

Exponent Law: Quotient

b^x / b^y = b^(x-y).

Exponent Law: Power

(b^x)^y = b^(xy).

Logarithm Law: Product

log_b(xy) = log_b(x) + log_b(y).

Logarithm Law: Quotient

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

Logarithm Law: Power

log_b(x^k) = k * log_b(x).

Special Logs: log_b(1)

log_b(1) = 0 because b⁰ = 1.

Special Logs: log_b(b)

log_b(b) = 1 because b¹ = b.

Growth Comparison: log(n) < n^ε

For any ε > 0, log(n) grows slower than any polynomial.

Growth Comparison: n^log_b(a) in Master Theorem

The term n^log_b(a) often appears as a critical growth factor in the Master Theorem, a method used to solve recurrence relations of the form T(n) = aT(n/b) + f(n) for divide and conquer algorithms.

• ‘a’ represents the number of subproblems.

• ‘n/b’ is the size of each subproblem.

• ‘f(n)’ is the cost of the work done outside the recursive calls (e.g., combining solutions)

Common Pitfalls: 2 * log₂(n) ≠ n

Multiplying a log by 2 does not equal n; only 2^log₂(n) = n.

Common Pitfalls: base of log

In CS and in math, log often means log₂.

Pitfall: log(n²) vs (log(n))²

log(n²) = 2*log(n); beware that (log(n))^2 is NOT the same as log(n^2).