1
$\begingroup$

There are a number of way to compute the permanent, and I'm wondering between the Ryser's formula, the Balasubramanian-Bax-Franklin, and the Glynn formula, whether there is a noticeable difference in computational speed. On Wikipedia, it says that the latter two formulas are just as fast as Ryser's, but then says that they may in fact be twice as fast. Is there a way to mathematically prove that one or the others are superior in efficiency?

$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

Glynn's formula has a time-complexity of $$O(n2^n)$$ whereas, Ryser's formula has a time-complexity of $$O(n^22^n)$$ So, Glynn's formula is the most efficient general purpose algorithm for computing the permanent. However, some special cases have faster algorithms as briefly explained in the source below.

Source: https://arxiv.org/pdf/1706.01260.pdf

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .