[larsrc]

There are variations, that's what we learned back at Uni. Expected O(f(n)), average O(f(n)), amortised O(f(n)), even expected amortised O(f(n)). "Expected" implied a randomised algorithm.

[tsimionescu]

> "Expected" implied a randomised algorithm.

Not necessarily. It can be the "expected" number of steps over the range of unknown inputs even for a deterministic algorithm.