Outlier detection in small sets

Question

Is there a good algorithm for detecting outliers in small sets of decimal numbers? The best idea I have come up with so far is a kind of recursive standard deviation based approach, but it seems a bit computationally expensive.

I'm using c++, so any existing functionality in say Boost or other maths helper libraries is welcome in your answers.

Thanks.

Answer 1

You can do it in O(n) time with an online variance algorithm (http://en.wikipedia.org/wiki/Algorithms_for_calculating_variance#Online_algorithm) and then a second pass to mark outliers.