Suppose that I have a system of $2\times2^{N(N-1)}$ equations that I managed to reduce to a system of $2N\times 2^{N-1}$ equations.
Is there a way to express the computational advantages brought by such a reduction? I was thinking about something with Big o notation, but I am not sure that it is appropriate for the case.
Well, there are $\frac{2^{(N-1)^2}}{N}$ as many equations in the first case compared to the second. The computational advantage to this reduction is determined by how the algorithm that is supposed to go to work on these equations scales. If for instance your algorithm scales as $\mathcal{O}(n^2)$, and we let the reduced number of equations be $n$, the reduction in computational complexity would be
$$\mathcal{O}\left(n^2 \left( \frac{2^{(N-1)^2}}{N}\right)^2\right)\rightarrow \mathcal{O}(n^2),$$
so the runtime could be expected to decrease by a factor of $$\left(\frac{2^{(N-1)^2}}{N}\right)^2$$ ... but it all depends on the algorithm.