On: The Median of a Trillion Numbers

[eru]

Calculating the average is in O(n). Calculating the median is in O(n).

[roundsquare → eru]

Actually, even be worse here. E.g. if all the numbers are positive you will get an overflow pretty quick, so you'll need a better datatype. So if you are dealing with b-bit numbers you'd need O(n * log(bn)) to calculate the average.

(Usually this doesn't matter, but since n >> b it does).

Edit: Notwithstanding my earlier comment that average doesn't work, merely commenting on the run time of average.

[bravura → roundsquare]

Or, you could compute the average as follows:

    m <-- m - (1/t) (m - x_t)

This will compute the exact historical average. I like to use 2/t instead of 1/t to get a moving average over a non-stationary distribution, which favors the more recent events.

[eru → bravura]

Please keep numerical errors in mind. They accumulate.