Nielsen and Chuang's proof for 'approximating arbitrary unitary gates is generically hard'

Question

The following statement is found on the page 199 of Nielsen and Chuang's book (10th Anniversary Edition) in the proof for the fact that 'approximating arbitrary unitary gates is generically hard':

Suppose we have $g$ different types of gates available, and each gate works on at most $f$ input qubits. These numbers, $f$ and $g$, are fixed by the computing hardware we have available, and may be considered to be constants. Suppose we have a quantum circuit containing m gates, starting from the computational basis state $|0⟩^{\bigotimes n}$. For any particular gate in the circuit there are therefore at most$\binom{n}{f}^g=O(n^{fg})$ possible choices.

I kind of think the number of possible choices for any particular gate is more in line with $\binom{n}{f}\cdot g=O(n^fg)$. What do you think?

Answer 1

You are right. There is a choice for place and there is a choice for gate. Then we just multiply the number of choices.
But it's even stronger limitation on the number of possible states that we can obtain. So the general reasoning is still correct.