Interpretation of "expected cost" of an algorithm
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}$.

But what the expected cost gives you is the average of costs. If you repeat the algorithm and make the average of the cost (after an infinite number of times) you will get an average cost equal to the expected cost.

I hope it's clear ...