Is every reduction function $f \in O(n)$?
I'm not sure exactly what you mean. In essentially all interesting cases, $L_1$&nbsp;is infinite, so you can't say that $|L_1|=n$. Second, the function $f$ is a function from strings to strings, so it doesn't make sense to ask if it's $O(n)$ because $O(\cdot)$ is a class of functions from numbers to numbers.

However, you're most probably asking if all reductions are in $\mathrm{TIME}[O(n)]$, i.e., if they can all be computed in linear time. They can't.

By the time hierarchy theorem, for any $r&gt;s$, there are languages in $\mathrm{TIME}[O(n^r)]$ that are provably not in $\mathrm{TIME}[O(n^s)]$. So, consider any problem&nbsp;$X$ that is P-complete under polynomial-time reductions. We must have $X\in\mathrm{TIME}[O(n^s)]$ for some&nbsp;$s$. By the time hierarchy theorem, there is some langauge $Y\in\mathrm{TIME}[O(n^{s+1})]\setminus\mathrm{TIME}[O(n^s)]$.  Since $X$&nbsp;is P-complete and $Y\in{}$P, there must be some polynomial-time reduction $Y\to X$. However, this reduction cannot run in linear time. If the reduction did run in linear time, there would have to be some&nbsp;$k$ such that it transforms every length-$n$ instance of&nbsp;$Y$ into an instance of&nbsp;$X$ with length at most $kn$ (a function running in linear time can only produce linearly much output). But, then, we would be able to decide&nbsp;$Y$ via the reduction in time
$$O(n) + O((kn)^s) = O(n) +O(n^s) =O(n^s)\,,$$
contradicting our choice of $Y\notin\mathrm{TIME}[O(n^s)]$.

Note that, in general, if we're talking about computability rather than complexity, we only care that the reduction is computable&nbsp;&ndash; we usually don't care about its time or space complexity at all. However, in other contexts, we do care about linear-time reductions, for example in proving problems hard under the exponential time hypothesis.