# Interpretation of “expected cost” of an algorithm

I'm studying randomized algorithms and I sometimes come across results like

(1) The algorithm has an expected $O(f(n))$ cost.

and

(2) With constant probability, the cost is bounded by $O(f(n))$.

I'm perfectly fine with statements like (2), but I'm puzzled to what extent a statement like (1) is useful: For certain probability distributions of a random variable, the expected value itself occurs with less than constant probability; for other distributions, it occurs with $1-1/n$ probability. Of course, in many cases, (1) is extended via concentration bounds to show high probability, but in cases where this isn't done, it doesn't seem that a statement on the "expected cost" lets us derive any implications on the actual performance of the algorithm, right?

If you have a cost of $1$ with probability one half and $0$ with probability one half, you never reach the expected cost of $\frac{1}{2}$.