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?
Interpretation of expected cost of an algorithm
probability theory;randomized algorithms