In financial and scientific data analysis applications, such as in spotting trends in stocks, we are often interested in making sense of noisy or highly fluctuating data. One method to achieve this goal is to take an average of recent values, as shown in Figure 25.4. For instance, in using a weighted moving average, one begins by specifying a sequence of m weights, W = (w₀, w₁,...,w_m−1), with 

Typically, one chooses the weights so that wi > wi+1, for i = 1,...,n − 1, so as to give greater emphasis to recent data. Then, given a sequence of n ≥ m data values, X = (x₀, x₁,...,x_n−1), the ith value of the weighted moving average is computed as 

A_i = w₀a_i + w₁a_i−1 + w₂a_i−2 + ··· . 

For example, if W = (0.5, 0.3, 0.2) and the three most recent data values were 136, 150, 200, then the current weighted moving average would be 

A_i = 0.5(136) + 0.3(150) + 0.2(200) = 153, 

which is closer to 136 than it is to 200. Given the sequences W and X, as specified above, describe an efficient method for computing all the A_i values, for i = 0, 1,...,n − 1, using O(n log n) arithmetic operations. 

-1 W; = 1 i=0