Why is the variance of the running time never mentioned when studying randomised algorithms?
Forgive if I am wrong about this by the way. I'm doing what would be called a major in Applied Math with a minor in Statistics over in America. I decided to self study algorithms just for the fun of it. I got Introduction to Algorithms by Cormen for cheap and started going through it. Whenever randomised algorithms were discussed however they only presented results on the expected value of the running time. Googling seems to suggest that this is the case in general.
My point is that wouldn't it be very useful to know the variance? I can think of the following reasons to know it:
- It gives you a measure of how much variation there is in the running time (obviously)
- You can estimate the total running time for running the algorithm many times by using the central limit theorem. For example this could be useful if a non-randomised algorithm calls a randomised one many times (more formally Ω(1) times with a large enough constant) inside a for loop, and you want to estimate the running time of the "outer" algorithm.
- If you are trying to do an experiment to find the constants hidden by the Big-O notation, it will be easier to do inference statistically if you have an idea what the variance looks like (a little contrived, but still)
I am curious, is it just that its too hard to derive results or is it a cultural thing in CS? By cultural I mean would CS a tendency to care less about this like engineers care less about real analysis, or pure mathematicians care less about fluid mechanics (I know I'm in danger of over generalising, but you get my drift).
EDIT Cleaned up writing
Posted Dec 2, 2011, 1:19 AM UTC · edited