How to construct this oracle quantum gate?

I was reading the paper Quantum Computational Complexity in the Presence of Closed Timelike Curves.
In this the author mentions that following quantum oracle gate which operates on $n+1$ qubits, can be constructed with $p(n)$ gates, where $p(n)$ is some polynomial in $n$.
$$U_{f}=\sum_{i=0} ^{2^{n-1}}|i\rangle \langle i| \otimes \sigma_{x}^{f(i)}$$ Where $\sigma_{x}$ is Pauli matrix $X$ and $f:\{0,1\}^{n} \to \{0,1\}.$

How do I go about proving it. And what does polynomial number of gates mean. If suppose I prove that the above gate can be achieved using $n^2$ gates, I can club all the gates into one big gate and say it is done in a constant gate (i.e. one gate).