Functions — Domain, Range, and Composition
Pillar: CHAIN — "Functions are chains: output of one feeds into the next."
What Is a Function?
A function is a rule that takes an input and produces exactly one output. We write \(f(x) = 2x + 3\) to mean: "give me any number \(x\), and I will double it and add 3."
The key word is exactly one. For every input, there is a single, determined output. If you put in \(x = 5\), you always get \(f(5) = 13\). Never sometimes 13, sometimes 14. This determinism is what makes functions useful in programming and mathematics alike.
Formal definition. A function \(f: A \to B\) is a rule that assigns to each element \(a \in A\) exactly one element \(f(a) \in B\).
- \(A\) is the domain — the set of allowed inputs.
- \(B\) is the codomain — the set where outputs live.
- The range (or image) is the subset of \(B\) that actually gets hit: \(\{f(a) : a \in A\}\).
Why This Matters in Competitive Programming
Every time you write a function in code, you are defining a mathematical function. When you analyze time complexity, you are studying the function \(T(n)\). When you binary search, you rely on a function being monotonic. Understanding functions precisely — their domains, their behavior, how they compose — is the language of algorithm analysis.
Domain and Range
The domain is what you are allowed to feed in. The range is what you actually get out.
Finding the Domain
For most expressions, the domain is "all real numbers" unless something breaks. The three common breakdowns:
| Danger | Example | Restriction |
|---|---|---|
| Division by zero | \(f(x) = \frac{1}{x-3}\) | \(x \neq 3\) |
| Square root of negative | \(g(x) = \sqrt{x - 2}\) | \(x \geq 2\) |
| Logarithm of non-positive | \(h(x) = \log(x)\) | \(x > 0\) |
Example 1. Find the domain of \(f(x) = \frac{\sqrt{x+1}}{x - 4}\).
Two restrictions combine:
- Square root needs \(x + 1 \geq 0\), so \(x \geq -1\).
- Denominator needs \(x \neq 4\).
Domain: \([-1, 4) \cup (4, \infty)\).
Example 2. Find the domain of \(g(x) = \frac{1}{\sqrt{x^2 - 9}}\).
- The square root needs \(x^2 - 9 > 0\) (strictly positive, since it is in the denominator).
- \(x^2 > 9\) means \(x > 3\) or \(x < -3\).
Domain: \((-\infty, -3) \cup (3, \infty)\).
Finding the Range
The range is harder. Strategy: set \(y = f(x)\) and solve for \(x\) in terms of \(y\). The values of \(y\) for which a solution exists form the range.
Example. Find the range of \(f(x) = \frac{2x+1}{x-3}\).
Set \(y = \frac{2x+1}{x-3}\) and solve for \(x\):
This is defined for all \(y \neq 2\). So the range is \(\mathbb{R} \setminus \{2\}\) — all real numbers except 2.
Function Evaluation
Evaluating a function means substituting the input and computing.
| Input | Computation | Output |
|---|---|---|
| \(f(0)\) | \(0 - 0 + 5\) | \(5\) |
| \(f(2)\) | \(4 - 6 + 5\) | \(3\) |
| \(f(-1)\) | \(1 + 3 + 5\) | \(9\) |
| \(f(a+1)\) | \((a+1)^2 - 3(a+1) + 5\) | \(a^2 - a + 3\) |
That last row matters. Functions accept expressions, not just numbers. In competitive programming, you constantly evaluate functions at expressions — \(T(n/2)\), \(f(f(x))\), \(\text{dp}[i-1] + \text{cost}(i)\).
Inverse Functions
An inverse function "undoes" the original. If \(f(x) = 2x + 3\), then \(f\) takes 5 to 13. The inverse \(f^{-1}\) takes 13 back to 5.
Formal definition. \(f^{-1}(y) = x\) if and only if \(f(x) = y\).
Finding the Inverse
- Write \(y = f(x)\).
- Solve for \(x\) in terms of \(y\).
- Swap the names: the expression you get is \(f^{-1}(y)\).
Example. Find the inverse of \(f(x) = 2x + 3\).
So \(f^{-1}(x) = \frac{x - 3}{2}\).
Verification: \(f(f^{-1}(x)) = 2 \cdot \frac{x-3}{2} + 3 = x - 3 + 3 = x\). It undoes the function.
When Does the Inverse Exist?
A function has an inverse only if it is one-to-one (injective): different inputs always give different outputs. Graphically, this is the horizontal line test — no horizontal line crosses the graph more than once.
\(f(x) = x^2\) is NOT one-to-one on all reals because \(f(3) = f(-3) = 9\). But if you restrict the domain to \(x \geq 0\), it becomes one-to-one, and the inverse is \(f^{-1}(x) = \sqrt{x}\).
Why Inverses Matter
In competitive programming, inverses appear constantly:
- Modular inverse: if \(f(x) = ax \mod m\), the inverse finds \(x\) from \(ax \mod m\).
- Binary search: you have \(f(x)\), you want the \(x\) that gives a target \(y\) — that is finding \(f^{-1}(y)\).
- Encoding/decoding: hash functions, coordinate compression, rank/unrank operations.
Function Composition
Composition chains two functions: the output of one becomes the input of the next.
Read this as "f of g of x." First apply \(g\), then apply \(f\) to the result.
Example
Let \(f(x) = 2x + 3\) and \(g(x) = x^2\).
Notice: \(f(g(x)) \neq g(f(x))\) in general. Composition is not commutative. Order matters.
Trace Table
For \(x = 4\):
| Step | \(g(x) = x^2\) | \(f(\cdot) = 2(\cdot) + 3\) | Result |
|---|---|---|---|
| \(f(g(4))\) | \(g(4) = 16\) | \(f(16) = 35\) | \(35\) |
| \(g(f(4))\) | \(f(4) = 11\) | \(g(11) = 121\) | \(121\) |
Decomposing Complex Functions
Given a complicated function, can you break it into simpler compositions?
Let \(g(x) = 3x + 7\) and \(f(x) = \sqrt{x}\). Then \(h(x) = f(g(x))\).
This skill matters because it reveals structure. In algorithm design, recognizing that a complex transformation is a chain of simple transformations lets you optimize each step independently.
Composition with Itself
\(f(f(x))\) is called the second iterate of \(f\). If \(f(x) = 2x + 1\):
Pattern: \(f^{(n)}(x) = 2^n x + (2^n - 1)\). Recognizing patterns in iterated functions is key to solving recurrences, which we cover in Lesson 4.
Even and Odd Functions
Even function: \(f(-x) = f(x)\) for all \(x\). The graph is symmetric about the \(y\)-axis.
- Examples: \(f(x) = x^2\), \(f(x) = |x|\), \(f(x) = \cos(x)\)
Odd function: \(f(-x) = -f(x)\) for all \(x\). The graph is symmetric about the origin.
- Examples: \(f(x) = x^3\), \(f(x) = x\), \(f(x) = \sin(x)\)
Testing
Is \(f(x) = x^3 + x\) even, odd, or neither?
It is odd.
Is \(g(x) = x^2 + x + 1\) even, odd, or neither?
This is neither \(g(x)\) nor \(-g(x)\). So \(g\) is neither.
Key Properties
| Property | Even \(f\) | Odd \(f\) |
|---|---|---|
| \(f(0)\) | any value | must be \(0\) |
| Sum of even + even | even | - |
| Sum of odd + odd | - | odd |
| Product of even \(\times\) even | even | - |
| Product of odd \(\times\) odd | even | - |
| Product of even \(\times\) odd | odd | - |
Why This Matters
Parity (even/odd) shows up in competitive programming when you exploit symmetry to halve computation. If a function is even, you only need to compute it for non-negative inputs. If a sum involves an odd function over a symmetric range, it cancels to zero.
Piecewise Functions
A piecewise function uses different rules for different parts of the domain:
Evaluate: \(f(-3) = -3 + 1 = -2\), \(f(2) = 4\), \(f(0) = 0\).
The absolute value function is piecewise:
In competitive programming, piecewise logic appears in min, max, absolute differences, and penalty functions. Recognizing the piecewise structure helps you handle edge cases correctly.
Practice Problems
Problem 1. Find the domain of \(f(x) = \frac{1}{\sqrt{5 - x}} + \log(x + 2)\).
Solution
Two restrictions: \(5 - x > 0\) gives \(x < 5\); \(x + 2 > 0\) gives \(x > -2\). Domain: \((-2, 5)\).
Problem 2. If \(f(x) = 3x - 7\), find \(f^{-1}(x)\) and verify that \(f(f^{-1}(x)) = x\).
Solution
\(y = 3x - 7 \implies x = \frac{y+7}{3}\). So \(f^{-1}(x) = \frac{x+7}{3}\). Verify: \(f\!\left(\frac{x+7}{3}\right) = 3 \cdot \frac{x+7}{3} - 7 = x + 7 - 7 = x\).
Problem 3. Let \(f(x) = x + 1\) and \(g(x) = 2x\). Compute \(f(g(3))\), \(g(f(3))\), and \(f(f(f(0)))\).
Solution
\(f(g(3)) = f(6) = 7\). \(g(f(3)) = g(4) = 8\). \(f(f(f(0))) = f(f(1)) = f(2) = 3\).
Problem 4. Decompose \(h(x) = (5x - 1)^3\) into \(f(g(x))\). What are \(f\) and \(g\)?
Solution
\(g(x) = 5x - 1\), \(f(x) = x^3\). Then \(f(g(x)) = (5x-1)^3 = h(x)\).
Problem 5. Classify each function as even, odd, or neither: (a) \(f(x) = x^4 - x^2\), (b) \(g(x) = x^3 - 2x\), (c) \(h(x) = x^2 + x\).
Solution
(a) \(f(-x) = x^4 - x^2 = f(x)\): even. (b) \(g(-x) = -x^3 + 2x = -g(x)\): odd. (c) \(h(-x) = x^2 - x \neq h(x)\) and \(\neq -h(x)\): neither.
Problem 6. The function \(f(x) = \frac{x}{x+1}\) for \(x \neq -1\). Compute \(f(f(x))\) and simplify.
Solution
\(f(f(x)) = f\!\left(\frac{x}{x+1}\right) = \frac{\frac{x}{x+1}}{\frac{x}{x+1}+1} = \frac{\frac{x}{x+1}}{\frac{x + x + 1}{x+1}} = \frac{x}{2x+1}\).