A

first order linear recurrence is defined as:

p_{1} = b_{1}

p_{i} = a_{i}p_{i-1} + b_{i}

The problem is, given b_{1} ... b_{n} and
a_{1} ... a_{n}, find all the values of p. Sequentially, the straightforward algorithm is to compute p_{2} by replacing p_{1} in the equation, and so on, the algorithm will take O(n) time.

In parallel, it at first seems that there is not much room for parallelization, since p_{i} needs the value of p_{i-1}. However, there are actually several ways to do this in O(log n) steps using O(n) processors. One possible algorithm is to use a prefix summing algorithm, another is to use a technique called odd-even reduction.