Exponents, Logarithms, and Radicals
Pillar: FIX — "Fix the base, the exponent tells you everything."
Exponent Laws Review
Exponents are repeated multiplication, just as multiplication is repeated addition. The laws below govern how exponents combine, and you will use them constantly in algorithm analysis.
The Core Laws
Let \(a > 0\) and \(m, n\) be any real numbers.
| Law | Formula | Example |
|---|---|---|
| Product | \(a^m \cdot a^n = a^{m+n}\) | \(2^3 \cdot 2^5 = 2^8 = 256\) |
| Quotient | \(\frac{a^m}{a^n} = a^{m-n}\) | \(\frac{3^7}{3^4} = 3^3 = 27\) |
| Power of a power | \((a^m)^n = a^{mn}\) | \((2^3)^4 = 2^{12} = 4096\) |
| Power of a product | \((ab)^n = a^n b^n\) | \((6)^2 = 2^2 \cdot 3^2 = 36\) |
| Power of a quotient | \(\left(\frac{a}{b}\right)^n = \frac{a^n}{b^n}\) | \(\left(\frac{2}{3}\right)^3 = \frac{8}{27}\) |
Special Exponents
| Expression | Value | Why |
|---|---|---|
| \(a^0\) | \(1\) | \(a^n / a^n = a^{n-n} = a^0\), and \(a^n / a^n = 1\) |
| \(a^{-n}\) | \(\frac{1}{a^n}\) | \(a^0 / a^n = a^{-n}\), and \(a^0 = 1\) |
| \(a^1\) | \(a\) | By definition |
Example. Simplify \(\frac{2^{15} \cdot 3^4}{2^{12} \cdot 3^2}\).
Why This Matters
Binary exponentiation — computing \(a^n \bmod m\) in \(O(\log n)\) — is one of the most fundamental algorithms in competitive programming. It works by decomposing \(n\) into powers of 2 and using the product law: \(a^{13} = a^8 \cdot a^4 \cdot a^1\). The exponent laws are not just algebra; they are the foundation of fast exponentiation.
Fractional Exponents and Radicals
Radicals and fractional exponents are two notations for the same thing:
Key Examples
| Expression | As radical | Value |
|---|---|---|
| \(8^{1/3}\) | \(\sqrt[3]{8}\) | \(2\) |
| \(16^{3/4}\) | \((\sqrt[4]{16})^3 = 2^3\) | \(8\) |
| \(27^{2/3}\) | \((\sqrt[3]{27})^2 = 3^2\) | \(9\) |
| \(4^{-1/2}\) | \(\frac{1}{\sqrt{4}}\) | \(\frac{1}{2}\) |
Simplifying Radicals
To simplify \(\sqrt{n}\), factor \(n\) and pull out perfect squares.
You can only combine radicals with the same radicand (the number under the root).
Rationalizing the Denominator
To eliminate a radical from the denominator, multiply by the conjugate:
Logarithms
The logarithm answers: "What exponent turns the base into this number?"
Reading: "\(\log\) base \(b\) of \(x\) equals \(y\)" means "\(b\) raised to \(y\) gives \(x\)."
Building Intuition
| Question | Exponential form | Answer |
|---|---|---|
| \(\log_2 8 = ?\) | \(2^? = 8\) | \(3\) |
| \(\log_3 81 = ?\) | \(3^? = 81\) | \(4\) |
| \(\log_{10} 1000 = ?\) | \(10^? = 1000\) | \(3\) |
| \(\log_5 1 = ?\) | \(5^? = 1\) | \(0\) |
| \(\log_2 \frac{1}{4} = ?\) | \(2^? = \frac{1}{4}\) | \(-2\) |
The logarithm is the inverse function of the exponential. If \(f(x) = b^x\), then \(f^{-1}(x) = \log_b x\). This connects directly to Lesson 1: every invertible function has an inverse, and the exponential/logarithm pair is the most important one in computer science.
Logarithm Properties
These follow directly from the exponent laws, because logarithms are exponents.
| Property | Formula | From exponent law |
|---|---|---|
| Product rule | \(\log_b(xy) = \log_b x + \log_b y\) | \(b^{m+n} = b^m \cdot b^n\) |
| Quotient rule | \(\log_b\!\left(\frac{x}{y}\right) = \log_b x - \log_b y\) | \(b^{m-n} = \frac{b^m}{b^n}\) |
| Power rule | \(\log_b(x^k) = k \log_b x\) | \((b^m)^k = b^{mk}\) |
| Change of base | \(\log_b x = \frac{\log_c x}{\log_c b}\) | Convert via any base \(c\) |
| Identity | \(\log_b b = 1\) | \(b^1 = b\) |
| Identity | \(\log_b 1 = 0\) | \(b^0 = 1\) |
| Inverse | \(b^{\log_b x} = x\) | Definition |
| Inverse | \(\log_b(b^x) = x\) | Definition |
Worked Examples
Example 1. Simplify \(\log_2 32 + \log_2 4\).
Example 2. Expand \(\log_3\!\left(\frac{x^2 \sqrt{y}}{z}\right)\).
Example 3. Compute \(\log_8 16\) using change of base.
Why Logarithms Dominate Algorithm Analysis
When you halve a problem at each step — binary search, merge sort, segment trees — the number of steps is \(\log_2 n\). The logarithm counts how many times you can divide by the base before reaching 1.
This is why \(O(\log n)\) appears everywhere. It is the cost of repeated halving.
Solving Exponential and Logarithmic Equations
Strategy: Make the Bases Match
Example. Solve \(2^{3x-1} = 16\).
Write \(16 = 2^4\), so \(2^{3x-1} = 2^4\), which gives \(3x - 1 = 4\), so \(x = \frac{5}{3}\).
Strategy: Take Logarithms of Both Sides
Example. Solve \(5^x = 200\).
Strategy: Convert Log Equation to Exponential
Example. Solve \(\log_3(2x + 1) = 4\).
Always check: \(2(40) + 1 = 81 > 0\), so the logarithm is defined.
Example. Solve \(\log_2(x) + \log_2(x - 2) = 3\).
\(x = 4\) or \(x = -2\). But \(\log_2(x)\) requires \(x > 0\) and \(\log_2(x-2)\) requires \(x > 2\). So \(x = 4\) is the only solution.
Floor and Ceiling Functions
The floor \(\lfloor x \rfloor\) is the greatest integer \(\leq x\). The ceiling \(\lceil x \rceil\) is the smallest integer \(\geq x\).
| \(x\) | \(\lfloor x \rfloor\) | \(\lceil x \rceil\) |
|---|---|---|
| \(3.7\) | \(3\) | \(4\) |
| \(-2.3\) | \(-3\) | \(-2\) |
| \(5.0\) | \(5\) | \(5\) |
Key Identities
These appear constantly in competitive programming:
Integer ceiling division (no floating point needed):
In C++: (a + b - 1) / b gives the ceiling of \(a/b\) for positive integers.
Floor division count. \(\lfloor n/k \rfloor\) counts how many multiples of \(k\) are in \([1, n]\).
Example. How many multiples of 7 are in \([1, 100]\)? Answer: \(\lfloor 100/7 \rfloor = 14\).
The Staircase Property
The function \(f(k) = \lfloor n/k \rfloor\) takes only \(O(\sqrt{n})\) distinct values as \(k\) ranges from \(1\) to \(n\). This is the "staircase" shape — the function stays constant over blocks of \(k\) values, then drops. This property is the basis of many number-theoretic optimizations you will see in later chapters.
Connecting It All
Exponents, logarithms, and floor/ceiling are not separate topics. They form a toolkit:
- Exponents describe growth. \(2^n\) is the number of subsets of an \(n\)-element set.
- Logarithms describe how many times you divide. \(\log_2 n\) is the depth of a balanced binary tree with \(n\) leaves.
- Floor/ceiling handle the discrete world. Real-valued formulas must be rounded for integer contexts.
When you see \(O(n \log n)\) for merge sort, every piece is here: \(n\) items, \(\log_2 n\) levels of halving, floor division decides which half each element goes to.
Practice Problems
Problem 1. Simplify \(\frac{6^5 \cdot 6^{-2}}{6^2}\).
Solution
\(= 6^{5 + (-2) - 2} = 6^1 = 6\).
Problem 2. Evaluate \(\log_4 64\).
Solution
\(4^? = 64\). Since \(4 = 2^2\) and \(64 = 2^6\), we need \(2^{2x} = 2^6\), so \(x = 3\).
Problem 3. Solve \(3^{2x+1} = 243\).
Solution
\(243 = 3^5\), so \(2x + 1 = 5\), giving \(x = 2\).
Problem 4. Compute \(\lfloor 17/3 \rfloor\) and \(\lceil 17/3 \rceil\).
Solution
\(17/3 = 5.67\), so \(\lfloor 17/3 \rfloor = 5\) and \(\lceil 17/3 \rceil = 6\). In code: 17/3 = 5 and (17 + 3 - 1)/3 = 19/3 = 6.
Problem 5. How many times can you halve \(n = 10^6\) before reaching \(\leq 1\)? Express as a formula.
Solution
\(\lfloor \log_2(10^6) \rfloor = \lfloor 19.93 \rfloor = 19\) halvings. In general, the answer is \(\lfloor \log_2 n \rfloor\).
Problem 6. Simplify \(\log_2(8^n \cdot 4^{n+1})\).
Solution
\(= \log_2(2^{3n} \cdot 2^{2(n+1)}) = \log_2(2^{3n + 2n + 2}) = 5n + 2\).
Problem 7. How many multiples of 13 are in the range \([1, 10^9]\)?
Solution
\(\lfloor 10^9 / 13 \rfloor = \lfloor 76923076.9 \rfloor = 76923076\).