title: Probability space and expected running time: what are they?
body: <p>I've come across an issue where I'm to calculate or state the expected running time of an algorithm, and to state the probability space of such a running time. I will be frank and say I really have no idea what I'm supposed to do. What's the difference between expected running time and average running time, and what is a probability space and why is this needed?</p>