The usual algorithms for computing variance and standard deviation work on the full data set. What if you have a time series and want the standard deviation for a moving window? You could do the computation from fresh every time the window is advanced, but surely there’s a better way.
Tag Archives: Algorithms
Welford’s method for computing variance
The standard deviation is a measure of how much a dataset differs from its mean; it tells us how dispersed the data are. A dataset that’s pretty much clumped around a single point would have a small standard deviation, while a dataset that’s all over the map would have a large standard deviation. Given a …
What is O(0)
If you have ever taken a course in algorithms or data structures you’ll have seen big-O notation. For example you’ll know that a bubble sort runs in O(n²) time and merge sort in O(n log n) time. Maybe you have been explained that with big-O adding and multiplying by constants doesn’t matter, so O(1000n+1000) is …
Almost always, almost everywhere
There are two precise mathematical terms with names that sound delightfully imprecise: almost always, and almost everywhere.
Sorting a linked list
For God’s sake, don’t try sorting a linked list — Steve Yegge Why would it be a bad idea to sort a linked list? A few things come to mind: To locate the nth item you have to go through the n-1 items that precede it. This makes the formulation of many sorting algorithms unusable …