Number of parameters is not determinant.
You can re-use a network as many times as u want, which implies a more complex gradient computation.
Besides gradient computation depends on the function used. There are gradients cheaper to compute than others.