# On the complexity of an oracle for a classical function

Let us assume that we have a classical function $$f:\{0\,;\,1\}^n\to\{0\,;\,1\}^m$$ which is efficiently computable. Then, its oracle is defined with $$\mathbf{U}_f\,|x\rangle\,|y\rangle=|x\rangle\,|y\oplus f(x)\rangle$$. I quite often read that if $$f$$ is efficiently computable, then so is $$\mathbf{U}_f$$. Why is it the case? Where is the computational cost of evaluating $$f$$ taken into account?

Since $$\mathbf{U}_f$$ is a permutation matrix, one can implement it with at most $$2^{n+m}$$ SWAP gates, but this is not very efficient. What am I missing?

Another related question is: given a permutation matrix, how can one find the appropriate CNOT/SWAP gates succession to implement it? Even if an efficient solution exists, how does one find it?