An efficient algorithm for computing the reliability of consecutive-k-out-of-n : F systems
Many algorithms for computing the reliability of linear or circular consecutive-k-out-of-n:F systems appeared in this Transactions. The best complexity estimate obtained for solving this problem is O(k(3) log(n/k)) operations in the case of i.i.d. components. Using fast algorithms for computing a selected term of a linear recurrence with constant coefficients, we provide an algorithm having arithmetic complexity O(k log(k) log(log(k)) log(n) + k(omega)) where 2 < omega < 3 is the exponent of linear algebra. This algorithm holds generally for linear, and circular consecutive-k-out-of-n: F systems with independent but not necessarily identical components.
consecutive-k-out-of-n : f systems