Moving average with varying window size

Hello All,

I will be receiving a sequence of numbers a_1,a_2,.....a_n (n ~ million). However, I am given one at a time. Now define

s_t = sum_i(a_i), i = floor(t/2),...,t.

At each round 't', the user inputs a_t, and I output s_t.

This can be easily computed with a space complexity O(n/2), by storing the last $n/2$ entries.

I am wondering if there is a constant space algorithm for this -- that is, I can store some quantities like s_t,s_{t-1},a_t, etc, but it should be a fixed number independent of n.

Please help me with this. I could not think of any, and I suspect it doesn't exist, but I have no proof.

Thank you,
mnssk.
Sign In or Register to comment.

Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

Categories