STEP-BY-STEP LESSON · §11.4
Exponential and Logarithmic Functions: Graphs and Orders
Connect logarithms to repeated multiplication and compare growth.
Before you begin
A positive integer power
For a positive integer k, aᵏ multiplies k copies of a. In a binomial term, the exponents count how many factors supplied each choice. They are not multipliers in front of the bases.
Function, domain and codomain
A function assigns exactly one permitted output to every input in its domain. Its codomain is the declared output set; some members of that set may never be reached. The same formula on another domain or codomain can have different properties. f(x) names the output at x; it is not multiplication.
Symbols
- log_b n
- exponent to which b must be raised to obtain n
Definitions and notation for this topic
Big O, big Omega and big Theta
f∈O(g); f∈Ω(g); f∈Θ(g)
For eventually nonnegative functions f(n) and eventually positive g(n) on integer inputs: O(g) means f(n)≤C g(n) for all n≥n₀; Ω(g) means c g(n)≤f(n) for all n≥n₀; Θ(g) requires both bounds. Suitable constants c,C>0 and a threshold n₀ must exist and be independent of n.
Big O alone is an upper bound, not necessarily a tight order. The common shorthand f=O(g) means membership in a class of bounds, not equality with one function. Ω(g) is unrelated to the sample-space name Ω.
Separate glossary example
For n≥1, 3n²≤3n²+2n+1≤6n², so 3n²+2n+1∈Θ(n²), using c=3,C=6,n₀=1.
Logarithm and repeated halving
log_b x=y ⇔ b^y=x
For real b>0, b≠1 and x>0, log_b x is the exponent y for which b^y=x. In growth analysis the base is usually a fixed b>1.
Changing between fixed bases greater than 1 multiplies the logarithm by a positive constant. Actual algorithms may round sizes; include that rounding in an exact operation count.
Separate glossary example
log₂8=3. For n≥1, n/2^k≤1 exactly when k≥log₂n, so the least nonnegative integer k is ⌈log₂n⌉.
Step by step
Step 1 / 6
Read the inverse relationship
For b>1, bˣ=n and x=log_b n express the same relationship. A logarithm finds the exponent.
For b>1, the exponential function is strictly increasing and has range (0,∞), so each positive n has exactly one logarithm to base b.
Worked example
How many times must 64 be divided by 2 to reach 1?
- We count division operations, beginning at 64 and stopping as soon as the value is 1.
- 64→32→16→8→4→2→1.
- Six divisions, because 64=2⁶; log₂64=6.
Compare growth beyond a few sample values
To say that a positive function grows strictly slower than another in the comparisons below, show that their ratio becomes smaller than any fixed positive bound for all sufficiently large inputs. This is stronger than finding one crossing point. A ratio that is multiplied by at most one fixed factor less than 1 at every later step will become arbitrarily small.
Worked example
Explain why log₂n, n, n² and 2ⁿ have this order of growth, although small inputs may suggest a different order.
First justify why repeatedly multiplying by q with 0<q<1 makes a bound arbitrarily small.
c=1/q−1>0; (1+c)ᵗ≥1+tc; qᵗ≤1/(1+tc)
Why: For integer t≥0, the inequality starts at t=0. If it holds at t, multiplying by 1+c gives at least (1+tc)(1+c)=1+(t+1)c+tc²≥1+(t+1)c, proving the next case. Taking positive reciprocals gives the bound for qᵗ. For any ε>0 choose t large enough that 1+tc>1/ε; then qᵗ<ε, and every larger integer t also works.
Compare n with n² for positive integer n.
n/n²=1/n
Why: For any positive bound ε, choosing n>1/ε makes the ratio less than ε. Every larger n also works.
Compare n² with 2ⁿ by tracking the ratio.
aₙ=n²/2ⁿ; n≥4 ⇒ aₙ₊₁/aₙ=(1+1/n)²/2≤25/32
Why: For n≥4, 1+1/n≤5/4. Hence a₄₊ₜ≤a₄(25/32)ᵗ=(25/32)ᵗ for integer t≥0. The first step shows this bound becomes arbitrarily small. Given any fixed C>0, make aₙ<1/C; then 2ⁿ>Cn² for every sufficiently large n.
Place n between consecutive powers of two.
2ᵏ≤n<2ᵏ⁺¹ ⇒ log₂n/n < (k+1)/2ᵏ
Why: The numerator is less than k+1, while the denominator is at least 2ᵏ. For k≥1 the successive upper-bound ratio is (k+2)/(2(k+1))≤3/4, so these bounds become arbitrarily small too. Every sufficiently large n lies in one of these later intervals.
Interpret the three ratio arguments.
log₂n / n → 0; n/n² → 0; n²/2ⁿ → 0
Why: Here →0 means: below every chosen positive bound from some point onward. The arguments establish successive strict growth differences, not just three inequalities at one chosen n. They do not claim the same ranking at every small input.
Try it yourself
Why can n³>2ⁿ at n=2 not disprove eventual exponential dominance? What would an argument about eventual growth have to establish?
Show worked answer
Separate an initial example from an eventual claim.
2³=8>4=2²
Why: This is one finite input. An eventual claim permits finitely many early reversals; it must be justified for every input past one fixed threshold. To compare growth classes strictly, control the ratio against every fixed positive bound rather than only one sample.
Optional self-check
Explain why log₄16=2 and log₂16=4 can nevertheless have the same growth order as functions of their input.
Show answer
For every positive input n, log₂n=2log₄n. The factor 2 is constant, so it changes values but not Theta order for large n.