max and min are both “easier” monoids than E essentially because of dominance relations; for any θ, there’s going to be a single x that dominates all others, in the sense that all other x′≠x can be excluded from consideration and have no impact on the outcome. Whereas when calculating E, the only x′ that can be excluded are those outside the distribution’s support.
max is even easier than min because it commutes with the outer max; not only is there a single x that dominates all others, it doesn’t necessarily even depend on θ (the problem can be solved as maxxmaxθf(θ,x) or maxθ,xf(θ,x)). As a concrete example, the best case for nearly any sorting algorithm is already-sorted input, whereas the worst case depends more on which algorithm is being examined.
To elaborate this formally,
maxθmaxxf(θ,x) is best-case
maxθminxf(θ,x) is worst-case
maxθExf(θ,x) is average-case
max and min are both “easier” monoids than E essentially because of dominance relations; for any θ, there’s going to be a single x that dominates all others, in the sense that all other x′≠x can be excluded from consideration and have no impact on the outcome. Whereas when calculating E, the only x′ that can be excluded are those outside the distribution’s support.
max is even easier than min because it commutes with the outer max; not only is there a single x that dominates all others, it doesn’t necessarily even depend on θ (the problem can be solved as maxxmaxθf(θ,x) or maxθ,xf(θ,x)). As a concrete example, the best case for nearly any sorting algorithm is already-sorted input, whereas the worst case depends more on which algorithm is being examined.