This is O(n) to start up, and O(1) for all subsequent averages. Feel free to get in touch with me if you need something more exotic.