# Deriving the Time Complexity of Ryser's Algorithm for Evaluating the Permanent of a Matrix

Ryser has shown that the permanent of an $$n \times n$$ matrix $$A=(a_{ij})$$ can be expressed as

\begin{align} Perm(A) = (-1)^n \sum_{s \subset [n]} (-1)^{|s|} \prod_{i=1}^n \sum_{j \in s} a_{ij}, \end{align}

where $$[n]=\{1,2,\dots,n\}$$. This algorithm runs in $$\mathcal{O}(2^{n-1}n^2)$$ time. I've been trying to derive this, but can't quite get the result. Here's my work so far.

The outer sum is over all non-empty subsets of $$[n]$$, of which there are $$2^n-1$$. We recall that the number of subsets of size $$r$$ is $${n \choose r}=\frac{n!}{r!(n-r)!}$$.

For each set $$s$$ in the outer sum we compute $$\sum_{j \in s} a_{ij}$$, which uses $$|s|-1$$ additions. Next, this sum sees the product $$\prod_{i=1}^n$$, which takes $$n-1$$ multiplications. This happens for each non-empty subset of $$[n]$$, so there are the following number of total additions:

\begin{align} \sum_{s \subset [n]} \left(|s|-1\right) &= \sum_{k=1}^n (k-1) {n \choose k} \\ &= \sum_{k=1}^n k {n \choose k} - \sum_{k=1}^n {n \choose k} \\ &= n \sum_{k=1}^n {n-1 \choose k-1} - \left(2^n - 1\right) \\ &= n \left( 2^{n-1}-1 \right) - \left(2^n - 1\right) \\ &=n2^{n-1} - 2^n -n +1. \end{align}

The total number of multiplications is $$(n-1)(2^n-1)$$.

There is also the $$(-1)^{|s|}$$, which takes another $$2^n-1$$ operations in total.

This gives us a grand total of $$n2^n + n 2^{n-1} - 2^n -2n+1$$, which is not correct. It looks like I'm off by a factor of $$n$$ on the second term here. Where am I going wrong?

For a given $$s$$, you do $$(|s|-1)n$$ additions, not $$|s|-1$$ additions: you have to compute the inner sum for each $$i\in [n]$$. Thus, you are missing a factor of $$n$$.