## Algorithms

Moderators: None (Apply to moderate this forum)
Number of posts: 762

This Forum Only

Moving average with varying window size Posted by mnssk on 1 Nov 2010 at 1:08 PM
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.

## Recent Jobs

Official Programmer's Heaven Blogs
Web Hosting | Browser and Social Games | Gadgets

Popular resources on Programmersheaven.com
Assembly | Basic | C | C# | C++ | Delphi | Flash | Java | JavaScript | Pascal | Perl | PHP | Python | Ruby | Visual Basic