An O (k sup 3 log[n over k]) Algorithm for the Consecutive-k-out-of-n: F System

The fastest generally recognized algorithms for computing the reliability of consecutive-k-out-of-n: F systems require O(n) time, for both the linear and circular systems. We present a new algorithm which requires O (k sup 3 log [n over k]) time. The algorithm may be extended to yield an O (n max{k sup 3 log [n over k], log n}) total time procedure for solving the combinatorial problem of counting the number of working states, with w working and n - w failed components, w = 1, 2, ...., n.